P9882 [EC Final 2021] Vision Test

庞教授有着非凡的视力。他能看到 4K 显示器上的像素。为了测试庞教授的视力，寿教授将展示给庞教授几个像素，并让庞教授猜测一条包含这些像素的直线。给定 $k$ 个像素，其坐标为 $(i, y_i)$（$0 \le i < k$），庞教授必须找到非负整数 $a, b$ 和 $c$（它们表示直线 $y = \frac{ax+b}{c}$），使得 $y_i = \lfloor \frac{ai+b}{c} \rfloor$ 对于所有 $0 \le i < k$ 成立。 寿教授将向庞教授提出多个问题。问题如下：寿教授有一个固定的数组 $x_1, \ldots, x_n$。对于每个问题，寿教授选择数组中的一个范围 $x_l, \ldots, x_r$。然后他定义 $y_i = x_{l+i}$ 对于 $0 \le i \le r - l$，并要求庞教授回答关于这些 $r-l+1$ 个像素 $(0, y_0), \ldots, (r-l, y_{r-l})$ 的问题。 请帮助庞教授回答所有问题。对于每个问题，输出 **按字典序最小** 的 $(c, a, b)$ **作为答案**。 保证当庞教授选择整个数组 $x_1, x_2, \dots, x_n$ 时，答案存在。因此，当庞教授选择该数组的一个区间时，答案总是存在的。

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。第二行包含 $n$ 个数字 $x_1, \ldots, x_{n}$（$0 \leq x_i \leq 10^9$）。 下一行包含一个整数 $q$（$1 \le q \le 10^5$），表示问题的数量。 接下来的 $q$ 行中的每一行包含两个整数 $l, r$（$1 \le l \le r \le n$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，且所有测试用例中 $q$ 的总和不超过 $10^5$。

按输入顺序输出每个问题的答案，每行包含三个整数 $a, b, c$。

题面翻译由 ChatGPT-4o 提供。