Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Войско дуболомов выстроилось поотрядно перед своим командующим Урфином Джюсом и ждет указаний.
Войско состоит из `N` отрядов, `i`-й отряд включает дуболомов, покрашенных в цвет `c_i`, и имеет
численность `a_i` (цвета отрядов могут повторяться). Урфин Джюс планирует `Q` операций, в `j`-й из которых будут
участвовать отряды с номерами от `l_j` до `r_j` включительно (отряд может участвовать и в нескольких операциях). Для каждой из
операций нужно выбрать командующего, им должен стать дуболом-капрал того цвета, в который покрашено наибольшее количество дуболомов-участников
операции. Если несколько цветов представлены одинаковым числом дуболомов, командовать будет
капрал цвета с наименьшим номером. Помогите Урфину определить всех требуемых командующих.
В первой строке ввода находятся два натуральных числа: `N` – количество отрядов (`1<=N<=10^5`) и Q (`1<=Q<=10^5`) – количество операций.
Затем следует `N` строк, по два числа в каждой: цвет (`1<=c_i<=10^5`) и численность (`1<=a_i<=10^5`) каждого из отрядов.
Затем следует `Q` строк, по два числа в каждой: номера первого и последнего отрядов (`1<=l_j<=r_j<=N`), которые примут участие
в операции с соответствующим номером.
Выведите строку из `Q` натуральных чисел, разделенных пробелами: цвета командующих в каждой из операций.
```sample Пример ввода
3 2
1 10
2 12
1 5
1 2
1 3
```
```sample Пример вывода
2 1
```
Начало
Рабочее место участника
Комбинированные алгоритмы (алгоритм Мо)