Description

庞教授有着非凡的视力。他能看到 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$ 时，答案存在。因此，当庞教授选择该数组的一个区间时，答案总是存在的。

Input Format

第一行包含一个整数 $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$。

Output Format

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

3
5
1 1 2 2 2
4
1 5
1 1
3 5
2 3
5
1 2 3 4 6
3
1 5
2 4
3 5
3
0 3 5
1
1 3

1 4 3
0 1 1
0 2 1
1 1 1
5 4 4
1 2 1
3 6 2
5 1 2

Hint

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