Pang 教授拥有非凡的视力，他能看清 4K 显示器上的像素。为了测试 Pang 教授的视力，Shou 教授会向他展示若干像素，并让他猜出包含这些像素的直线。给定 $k$ 个坐标为 $(i, y_i)$ ($0 \le i < k$) 的像素，Pang 教授必须找到非负整数 $a, b$ 和 $c$（表示直线 $y = \frac{ax+b}{c}$），使得对于所有 $0 \le i < k$，都有 $y_i = \lfloor \frac{ai+b}{c} \rfloor$。

Shou 教授会向 Pang 教授提出多个问题。问题描述如下：Shou 教授有一个固定的数组 $x_1, \dots, x_n$。对于每个问题，Shou 教授在数组中选择一个区间 $x_l, \dots, x_r$。然后他定义 $y_i = x_{l+i}$，其中 $0 \le i \le r - l$，并要求 Pang 教授回答关于这 $r - l + 1$ 个像素 $(0, y_0), \dots, (r - l, y_{r-l})$ 的问题。

请帮助 Pang 教授回答所有问题。对于每个问题，输出字典序最小的 $(c, a, b)$。

题目保证当 Pang 教授选择整个数组 $x_1, x_2, \dots, x_n$ 时，答案存在。因此，当 Pang 教授选择该数组的任意区间时，答案总是存在的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。第二行包含 $n$ 个整数 $x_1, \dots, x_n$ ($0 \le x_i \le 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$，表示该问题的答案。

样例

输入 1

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

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