E. Иглу-небоскреб
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

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

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

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

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

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

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

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

В первой строке содержатся числа n и q (1 ≤ n, q ≤ 105). В следующих n строках идут пары чисел ai, bi (1 ≤ ai, bi ≤ 109). Далее идут q запросов вида li, ri, ti по одному в каждой строке (1 ≤ li ≤ ri ≤ n, 0 ≤ ti ≤ 106). Все числа на входе целые.

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

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

Примеры
Входные данные
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
Входные данные
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