{"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_. 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.\n\nThe 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:\n\n1\\. Number _x_ lies on the interval from _l__i_ to _r__i_ inclusive (_l__i_ ≤ _x_ ≤ _r__i_).\n\n2\\. 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_.\n\nFor 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\n## Input\n\nThe 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\n## Output\n\nFor each journalists' query print the number of the walrus _x_ that meets the criteria, given in the statement. Print one number per line.\n\n[samples]","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] 只海象会建成 #cf_span[bi] 层。\n\n在现场报道的记者向主办方提出了 #cf_span[q] 个查询。每个查询由三个数 #cf_span[li], #cf_span[ri], #cf_span[ti] 组成。主办方对每个查询给出一个数 #cf_span[x]，满足：\n\n1. 数 #cf_span[x] 位于区间 #cf_span[li] 到 #cf_span[ri] 之间（含端点），即 #cf_span[li ≤ x ≤ ri]。\n\n2. 在时间 #cf_span[ti]，编号为 #cf_span[x] 的海象的摩天大楼高度，在区间 #cf_span[[li, ri]] 内所有海象的摩天大楼中最大。\n\n对于每个记者的查询，请输出满足上述条件的海象编号 #cf_span[x]。如果有多个可能的答案，输出任意一个即可。\n\n第一行包含两个数 #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]）。所有输入数字均为整数。\n\n对于每个记者的查询，输出满足题目所述条件的海象编号 #cf_span[x]。每行输出一个数字。\n\n## Input\n\n第一行包含两个数 #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]）。所有输入数字均为整数。\n\n## Output\n\n对于每个记者的查询，输出满足题目所述条件的海象编号 #cf_span[x]。每行输出一个数字。\n\n[samples]","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 \\leq 10^6 $.\n\nThe height of walrus $ i $ at time $ t $ is:\n$$\nh_i(t) = a_i + b_i \\cdot t\n$$\n\nFor each query $ (l, r, t) $, find:\n$$\nx \\in [l, r] \\quad \\text{such that} \\quad h_x(t) = \\max_{i \\in [l, r]} h_i(t)\n$$\n\nIf multiple such $ x $ exist, output any one.\n\n**Objective:** For each of the $ q $ queries, output such an $ x $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF91E","tags":["data structures","geometry"],"sample_group":[["5 4\n4 1\n3 5\n6 2\n3 5\n6 5\n1 5 2\n1 3 5\n1 1 0\n1 5 0","5\n2\n1\n5"],["5 4\n6 1\n5 1\n2 5\n4 3\n6 1\n2 4 1\n3 4 5\n1 4 5\n1 2 0","3\n3\n3\n1"]],"created_at":"2026-03-03 11:00:39"}}