该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目背景

小明最近一直在研究斐波那契数列。现在，他把斐波那契数列的递推式作了如下修改：

$A_{i} = k·A_{i-1} + A_{i-2}$ （其中 $k$ 是一个整数）

显然，如果知道了数列前两项 $A_0, A_1$的值以及整数 $k$ 的值，就可以生成一个数列。小明将这种数列命名为小明数列。注意：小明数列的下标是从 $0$ 开始的，也就是小明数列的第一个元素是 $A_0$，第二个元素是 $A_1$。

题目描述

给出一个包含 $n$ 个下标的集合 $B$，对于 $B$ 中的每个下标 $B_i$，将这些下标对应的小明数列 $A$ 中的元素提取出来，得到一个新的数列：$A_{B_1}, A_{B_2}, ……, A_{B_n},$

问：新数列中，值最大的元素以及值最小的元素对应的下标分别是多少？如果满足要求的下标有多个，请你回答下标数值最小的那一个。注意：对应的下标值必须是集合 $B$ 中的元素。

为了研究这个问题，小明按照他的递推式生成了 $T$ 个小明数列。对于每个小明数列，小明想知道以上问题的答案。

你能帮助他吗？

输入格式

第一行：包含一个整数 $n$，表示集合 $B$ 中包含的元素个数。

第二行：包含 $n$ 个非负整数 $B_1, B_2, ……, B_n$。数据保证 $B_i < B_{i+1} （1 ≤ i < n）$。

第三行：包含一个整数 $T$, 表示生成的小明数列个数。

接下来 $T$ 行：每行包含三个整数 $A_0, A_1, k$ 用来描述一个小明数列。

输出格式

共 $T$ 行，每行包含两个整数，表示对应数列的答案。

样例1输入

3
0 1 2
3
0 0 1
3 -2 2
-2 3 1

样例1输出

0 0
0 1
1 0

样例1解释

第一个数列：$0, 0, 0, 0,$ ……

对于集合 $B$ = { $0, 1, 2$ } 中的下标，新数列为 $A_0, A_1, A_2$ 即 $0, 0, 0$，该数列元素全为 $0$，最大值、最小值均为 $0$，集合 $B$ 中所有下标 $0, 1, 2$ 均满足要求，其中下标最小的是 $0$.

第二个数列：$3, -2, -1, -4, -9,$ ……

对于集合 $B$ = { $0, 1, 2$ } 中的下标，新数列为 $A_0, A_1, A_2$ 即 $3, -2, -1$，其中最大值为 $A_0 = 3$，输出下标 $0$，最小值为 $A_1 = -2$，输出下标 $1$

第三个数列：$-2, 3, 1, 4, 5,$ ……

对于集合 $B$ = { $0, 1, 2$ } 中的下标，新数列为 $A_0, A_1, A_2$ 即 $-2, 3, 1$，其中最大值为 $A_1 = 3$，输出下标 $1$，最小值为 $A_0 = -2$，输出下标 $0$

样例2输入

6
1 2 3 5 6 8
2
0 1 1
10 -6 1

样例2输出

8 1
2 1

样例2解释

第一个数列：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34$ ……

该数列即为斐波那契数列，对于集合 $B$ = { $1, 2, 3, 5, 6, 8$ } 中的下标，新数列为 $A_1, A_2, A_3, A_5, A_6, A_8$ 即 $1, 1, 2, 5, 8, 21$，其中最大值为 $A_8 = 21$，输出下标 $8$，最小值为 $A_1 = A_2 =1$，下标 $1 < 2$，输出下标 $1$

第二个数列：$10, -6, 4, -2, 2, 0, 2, 2, 4, 10$ ……

对于集合 $B$ = { $1, 2, 3, 5, 6, 8$ } 中的下标，新数列为 $A_1, A_2, A_3, A_5, A_6, A_8$ 即 $-6, 4, -2, 0, 2, 4$，其中最大值为 $A_2 = A_8 = 4$，下标 $2 < 8$，输出下标 $2$，最小值为 $A_1 =-6$，输出下标 $1$

数据范围

$100$% 的数据：$1 ≤ T ≤ 3 × 10^5，1 ≤ n ≤ 10^5，0 ≤ B_i ≤ 10^9，-10^7 ≤ A_0, A_1 ≤ 10^7，1 ≤ k ≤ 5 × 10^3$