Олимпиадный тренинг

Задача . E. Иглу-небоскреб

Задача

Сегодня на северном полюсе олимпиада по спортивному... строительству игрушечных иглу-небоскребов!

В соревновании принимают участие n моржей. Каждому моржу выдан уникальный номер от 1 до n. После старта каждый морж начинает строить свой собственный иглу-небоскреб. Изначально, в момент времени 0, высота небоскреба i-ого моржа равна a_i. Каждую минуту i-ый морж достраивает b_i этажей.

Журналисты, ведущие репортаж с места проведения олимпиады, делают q запросов организаторам. Каждый запрос характеризуется тройкой чисел l_i, r_i, t_i. На каждый запрос организаторы отвечают одним числом x, таким, что:

1. Число x лежит в диапазоне от l_i до r_i включительно (l_i ≤ x ≤ r_i).

2. Небоскреб моржа с номером x имеет наибольшую высоту среди небоскребов всех моржей из этого диапазона [l_i, r_i] в момент времени t_i.

На каждый запрос журналистов выведите номер моржа x, удовлетворяющего критериям выше. Если возможных ответов несколько, то выведите любой.

Входные данные

В первой строке содержатся числа n и q (1 ≤ n, q ≤ 10⁵). В следующих n строках идут пары чисел a_i, b_i (1 ≤ a_i, b_i ≤ 10⁹). Далее идут q запросов вида l_i, r_i, t_i по одному в каждой строке (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ t_i ≤ 10⁶). Все числа на входе целые.

Выходные данные

На каждый запрос журналистов выведите номер моржа x, удовлетворяющего критериям из условия, по одному в строке.

Примеры

№	Входные данные	Выходные данные
1	5 4 4 1 3 5 6 2 3 5 6 5 1 5 2 1 3 5 1 1 0 1 5 0	5 2 1 5
2	5 4 6 1 5 1 2 5 4 3 6 1 2 4 1 3 4 5 1 4 5 1 2 0	3 3 3 1

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет