{"problem":{"name":"[EC Final 2021] Vision Test","description":{"content":"Prof. Pang has an extraordinary vision. He can see the pixels on a 4K monitor. To test Prof. Pang's vision, Prof. Shou will show Prof. Pang several pixels and let Prof. Pang guess a straight line that","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9882"},"statements":[{"statement_type":"Markdown","content":"Prof. Pang has an extraordinary vision. He can see the pixels on a 4K monitor. To test Prof. Pang's vision, Prof. Shou will show Prof. Pang several pixels and let Prof. Pang guess a straight line that contains these pixels. Given $k$ pixels with coordinates $(i, y_i)$ ($0\\le i<k$), Prof. Pang must find nonnegative integers $a, b$ and $c$ (which represent the line $y=\\frac{ax+b}{c}$) such that $y_i=\\lfloor \\frac{ai+b}{c} \\rfloor$ for all $0\\le i<k$. \n\nProf. Shou will ask Prof. Pang multiple questions. They are given as follows: Prof. Shou has a fixed array $x_1,\\ldots, x_n$. For each question, Prof. Shou chooses a range in the array, $x_l,\\ldots, x_r$. Then he defines $y_i=x_{l+i}$ for $0\\le i\\le r - l$ and asks Prof. Pang to answer the question for the $r-l+1$ pixels $(0, y_0), \\ldots, (r-l, y_{r-l})$.\n\nPlease help Prof. Pang answer all the questions. For each question, output the answer with the **minimum** $(c, a, b)$ **in lexical order**.\n\nIt is guaranteed that the answer exists when Prof. Pang chooses the whole array $x_1, x_2, \\dots, x_n$. So the answer always exists when Prof. Pang chooses an interval of this array.\n\n## Input\n\nThe first line contains a single integer $T$ ($1\\le T\\le 10^5$) denoting the number of test cases.\n\nFor each test case, the first line contains an integer $n$ ($1\\leq n\\leq 10^5$). The second line contains $n$ numbers $x_1, \\ldots , x_{n}$ ($0\\leq x_i\\leq 10^9$).\n\nThe next line contains an integer $q$ ($1\\le q\\le 10^5$) denoting the number of questions.\n\nEach of the following $q$ lines contains two integers $l, r$ ($1\\le l\\le r\\le n$). \n\nIt is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$ and that the sum of $q$ over all test cases will not exceed $10^5$.\n\n## Output\n\nIn the order of input, output one line with three integers $a, b, c$ denoting the answer for each question.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9882","tags":["2021","Special Judge","O2优化","ICPC","EC Final"],"sample_group":[["3\n5\n1 1 2 2 2\n4\n1 5\n1 1\n3 5\n2 3\n5\n1 2 3 4 6\n3\n1 5\n2 4\n3 5\n3\n0 3 5\n1\n1 3\n","1 4 3\n0 1 1\n0 2 1\n1 1 1\n5 4 4\n1 2 1\n3 6 2\n5 1 2\n"]],"created_at":"2026-03-03 11:09:25"}}