P9882 [EC Final 2021] Vision Test

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

The first line contains a single integer $T$ ($1\le T\le 10^5$) denoting the number of test cases. For 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$). The next line contains an integer $q$ ($1\le q\le 10^5$) denoting the number of questions. Each of the following $q$ lines contains two integers $l, r$ ($1\le l\le r\le n$). It 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$.

In the order of input, output one line with three integers $a, b, c$ denoting the answer for each question.