A8258 | Igloo Skyscraper

Today the North Pole hosts an Olympiad in a sport called... toy igloo skyscrapers' building!

There are $n$ walruses taking part in the contest. Each walrus is given a unique number from $1$ to $n$ . After start each walrus begins to build his own igloo skyscraper. Initially, at the moment of time equal to $0$ , the height of the skyscraper $i$ -th walrus is equal to $a_{i}$ . Each minute the $i$ -th walrus finishes building $b_{i}$ floors.

The journalists that are reporting from the spot where the Olympiad is taking place, make $q$ queries to the organizers. Each query is characterized by a group of three numbers $l_{i}$ , $r_{i}$ , $t_{i}$ . The organizers respond to each query with a number $x$ , such that:

1\. Number $x$ lies on the interval from $l_{i}$ to $r_{i}$ inclusive ( $l_{i}<=x<=r_{i}$ ).

2\. The skyscraper of the walrus number $x$ possesses the maximum height among the skyscrapers of all walruses from the interval $[l_{i},r_{i}]$ at the moment of time $t_{i}$ .

For each journalists' query print the number of the walrus $x$ that meets the above-given criteria. If there are several possible answers, print any of them.

The first line contains numbers $n$ and $q$ ( $1<=n,q<=10^{5}$ ). Next $n$ lines contain pairs of numbers $a_{i}$ , $b_{i}$ ( $1<=a_{i},b_{i}<=10^{9}$ ). Then follow $q$ queries i the following format $l_{i}$ , $r_{i}$ , $t_{i}$ , one per each line ( $1<=l_{i}<=r_{i}<=n$ , $0<=t_{i}<=10^{6}$ ). All input numbers are integers.

For each journalists' query print the number of the walrus $x$ that meets the criteria, given in the statement. Print one number per line.