English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
For each journalists' query print the number of the walrus _x_ that meets the criteria, given in the statement. Print one number per line.
[samples]
今天，北极举办了一场名为“玩具海象摩天大楼”建设的奥林匹克竞赛！
共有 #cf_span[n] 只海象参加比赛。每只海象被赋予一个从 #cf_span[1] 到 #cf_span[n] 的唯一编号。比赛开始后，每只海象开始建造自己的冰屋摩天大楼。在时间 #cf_span[0] 时，第 #cf_span[i] 只海象的摩天大楼高度为 #cf_span[ai]。每分钟，第 #cf_span[i] 只海象会建成 #cf_span[bi] 层。
在现场报道的记者向主办方提出了 #cf_span[q] 个查询。每个查询由三个数 #cf_span[li], #cf_span[ri], #cf_span[ti] 组成。主办方对每个查询给出一个数 #cf_span[x]，满足：
1. 数 #cf_span[x] 位于区间 #cf_span[li] 到 #cf_span[ri] 之间（含端点），即 #cf_span[li ≤ x ≤ ri]。
2. 在时间 #cf_span[ti]，编号为 #cf_span[x] 的海象的摩天大楼高度，在区间 #cf_span[[li, ri]] 内所有海象的摩天大楼中最大。
对于每个记者的查询，请输出满足上述条件的海象编号 #cf_span[x]。如果有多个可能的答案，输出任意一个即可。
第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 105]）。接下来 #cf_span[n] 行，每行包含一对数 #cf_span[ai], #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 109]）。随后是 #cf_span[q] 个查询，每个查询格式为 #cf_span[li], #cf_span[ri], #cf_span[ti]，每行一个（#cf_span[1 ≤ li ≤ ri ≤ n], #cf_span[0 ≤ ti ≤ 106]）。所有输入数字均为整数。
对于每个记者的查询，输出满足题目所述条件的海象编号 #cf_span[x]。每行输出一个数字。
## Input
第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 105]）。接下来 #cf_span[n] 行，每行包含一对数 #cf_span[ai], #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 109]）。随后是 #cf_span[q] 个查询，每个查询格式为 #cf_span[li], #cf_span[ri], #cf_span[ti]，每行一个（#cf_span[1 ≤ li ≤ ri ≤ n], #cf_span[0 ≤ ti ≤ 106]）。所有输入数字均为整数。
## Output
对于每个记者的查询，输出满足题目所述条件的海象编号 #cf_span[x]。每行输出一个数字。
[samples]
Given:
- $ n $ walruses, each with initial height $ a_i $ and growth rate $ b_i $, for $ i \in [1, n] $.
- $ q $ queries, each defined by $ (l, r, t) $, where $ 1 \leq l \leq r \leq n $, $ 0 \leq t \leq 10^6 $.
The height of walrus $ i $ at time $ t $ is:
$$
h_i(t) = a_i + b_i \cdot t
$$
For each query $ (l, r, t) $, find:
$$
x \in [l, r] \quad \text{such that} \quad h_x(t) = \max_{i \in [l, r]} h_i(t)
$$
If multiple such $ x $ exist, output any one.
**Objective:** For each of the $ q $ queries, output such an $ x $.
API Response (JSON)
{
"problem": {
"name": "E. Igloo Skyscraper",
"description": {
"content": "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_. Aft",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF91E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Today the North Pole hosts an Olympiad in a sport called... toy igloo skyscrapers' building!\n\nThere are _n_ walruses taking part in the contest. Each walrus is given a unique number from 1 to _n_. Aft...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "今天，北极举办了一场名为“玩具海象摩天大楼”建设的奥林匹克竞赛！\n\n共有 #cf_span[n] 只海象参加比赛。每只海象被赋予一个从 #cf_span[1] 到 #cf_span[n] 的唯一编号。比赛开始后，每只海象开始建造自己的冰屋摩天大楼。在时间 #cf_span[0] 时，第 #cf_span[i] 只海象的摩天大楼高度为 #cf_span[ai]。每分钟，第 #cf_span[i] 只...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given:\n- $ n $ walruses, each with initial height $ a_i $ and growth rate $ b_i $, for $ i \\in [1, n] $.\n- $ q $ queries, each defined by $ (l, r, t) $, where $ 1 \\leq l \\leq r \\leq n $, $ 0 \\leq t \\l...",
"is_translate": false,
"language": "Formal"
}
]
}