CF91E.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.

今天，北极举办了一场名为“玩具冰屋摩天大楼建造”的奥林匹克竞赛！

共有 $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 \le x \le r_i$）；

2. 在时刻 $t_i$，第 $x$ 号海象所建摩天大楼的高度，在所有编号属于区间 $[l_i, r_i]$ 的海象所建摩天大楼中达到最大值。

对每个记者的询问，请输出满足上述条件的海象编号 $x$。若存在多个可能的答案，输出其中任意一个即可。

The first line contains numbers n and q (1 ≤ n, q ≤ 105). Next n lines contain pairs of numbers a__i, b__i (1 ≤ a__i, b__i ≤ 109). 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 ≤ 106). All input numbers are integers.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）。接下来的 $n$ 行每行包含一对整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq 10^9$）。随后是 $q$ 个查询，每个查询格式为 $l_i$、$r_i$、$t_i$，每行一个（$1 \leq l_i \leq r_i \leq n$，$0 \leq t_i \leq 10^6$）。所有输入数据均为整数。

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

对于每位记者的查询，请输出满足题目中所述条件的海象 x 的编号。每行输出一个数字。