题目描述

sosusosu 虐爆 OI 之后成为了一名文化课选手。一天，他做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：

给定一个下标从 $0$ 开始，无限长的整数列 ${a_i},\ i\in \mathbb{N}$，已知 $a_0,a1$ 的值，以及递推式 $a{i+2}=k a_{i+1}+a_i,\ i\in\mathbb{N},k\in {\mathbb{N}^+}$。

sosusosu 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。

sosusosu 给了你一个集合 $S\subset \mathbb{N}$，他想问你对于 $S$ 中的每个数 $si$，使得 $a{s_i}$ 最大的 $si$ 和使得 $a{s_i}$ 最小的 $s_i$ 分别是多少。如果这样的 $s_i$ 有多个，请你回答最小的一个。

另外，sosusosu 准备对他作业中碰到的每个数列都让你回答一次，不过每次的集合 $S$ 是一样的。

输入格式

输入第一行一个整数 $m$ 表示 $S$ 中元素个数。
第二行 $m$ 个整数 $s_1,s_2,\cdots ,s_m$ 表示 $S$ 中的元素。保证它们是非负整数且严格递增（即 $si<s{i+1}$）。
第三行一个整数 $n$ 表示询问的数列个数。
接下来 $n$ 行每行三个整数 $a_0, a_1, k$ 描述一个数列。

输出格式

输出共 $n$ 行，每行依次输出两个整数 $\mathrm{maxsi},\mathrm{minsi}$，依次表示 $S$ 的元素 $si$ 中，使得 $a{s_i}$ 最大的 $si$ 和使得 $a{s_i}$ 最小的 $s_i$ 的值。如果这样的 $s_i$ 有多个，请你回答最小的一个。

样例 1

input

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

output

2 1
1 1

第一个数列的前 $9$ 项分别为 $10,-6,4,-2,2,0,2,2,4$，使得 $a_{s_i}$ 最大的 $s_i$ 为 $2$ 和 $8$（$a_2=a8=4$）其中 $2$ 较小，使得 $a{s_i}$ 最小的 $s_i$ 为 $1$（$a_1=-6$）。 第二个数列每项都等于 $0$，因此 $S$ 中的每个元素 $si$ 都既使 $a{si}$ 最大也使 $a{s_i}$ 最小，故答案是 $S$ 中最小元素。

样例 2

input

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

output

1 0
0 1

第一个数列的前 $4$ 项分别为 $-2,3,1,4$，使得 $a_{s_i}$ 最大的 $s_i$ 为 $1$（$a1=3$），使得 $a{s_i}$ 最小的 $s_i$ 为 $0$（$a0=-2$）。 第二个数列的前 $4$ 项分别为 $3,-2,-1,-4$，使得 $a{s_i}$ 最大的 $s_i$ 为 $0$（$a0=3$），使得 $a{s_i}$ 最小的 $s_i$ 为 $1$（$a_1=-2$）。

样例 3

input

29
2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912
4
10000000 10000000 100
9999984 -6180330 1
9999984 -6180329 1
-10000000 4142135 2

output

536870912 2
2 536870912
536870912 16
8 536870912

见附加文件（在页面上方下载）。其中除了前 3 个样例外还有约定分别和测试点 1, 9, 14 相同的样例各一个。

数据范围与提示

对于所有数据，$1\le n\le 3\times 10^5$，$1\le m\le 10^5$，$0\le s_i\le 10^9$，$-10^7\le a_0,a_1\le 10^7$，$1\le k\le 5\times 10^3$，保证 $s_i$ 严格单调递增。

注意，本题输入规模较大，请使用较快的方式读入。LOJ 上 C 语言的 scanf、C++ 的关闭同步的 cin、Pascal 的 read 读入此题数据时间均在 50 ~ 200 毫秒之间。

所有测试数据的范围和特点如下表所示：
（未标明的以上述所有数据的限制为准）