【问题描述】
sosusosu 虐爆 OI 之后成为了一名文化课选手。一天，他做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：
.
给定一个下标从 0 开始，无限长的整数列 ai, i ∈ N，已知 a0, a1 的值，已经递推式 $a_{i+2} = k\times a_{i+1} + a_i$, i ∈ N, k ∈ N+
sosusosu 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。
sosusosu 给了你一个集合 S ⊂ N，他想问你对于 S 中的每个数 si，使得 asi 最大的 si和使得 asi 最小的 si 分别是多少。如果这样的 si 有多个，请你回答最小的一个。
另外，sosusosu 准备对他作业中碰到的每个数列都让你回答一次，不过每次的集合 S是一样的。
【输入格式】
输入第一行一个整数 m 表示 S 中元素个数。
第二行 m 个整 s1, s2, ..., sm 表示 S 中的元素。保证它们是非负整数且严格递增 (即 si < si+1)。
第三行一个整数 n 表示询问的数列个数。
接下来 n 行每行三个整数 a0, a1, k 描述一个数列。
【输出格式】
输出共 n 行，每行依次输出两个整数 maxsi, minsi，依次表示 S 的元素 si 中，使得$a_{si}$ 最大的 si 和使得 $a_{si}$ 最小的 si 的值。如果这样的 si 有多个，请你回答最小的一个。
【样例 1 输入】 8 1 2 3 4 5 6 7 8 2 10 -6 1 0 0 1 【样例 1 输出】 2 1 1 1【样例 1 解释】
第一个数列的前 9 项分别为 10, −6, 4, −2, 2, 0, 2, 2, 4，使得 asi 最大的 si 为 2 和 8(a2 = a8 = 4) 其中 2 较小，使得 asi 最小的 si 为 (a1 = −6)。第二个数列每项都等于 0，因此 S 中的每个元素 si 都既使 asi 最大也使 asi 最小，故答案是 S 中最小元素。
【样例 2 输入】 3 0 1 2 2 -2 3 1 3 -2 2 【样例 2 输出】 1 0 0 1【样例 2 解释】
第一个数列的前 4 项分别为 −2, 3, 1, 4，使得 asi 最大的 si 为 1(a1 = 3)，使得 asi 最小的 si 为 0(a0 = −2)。第二个数列的前 4 项分别为 3, −2, −1, −4，使得 asi 最大的 si 为 0(a0 = 3)，使得 asi 最小的 si 为 1(a1 = −2)。
大样例
其中除了前 3 个样例外还有约定分别和测试点 1, 9, 14 相同的样例各一个。
【数据规模与约定】
对于所有数据，$1 ≤ n ≤ 3 × 10^5, 1 ≤ m ≤ 10^5, 0 ≤ si ≤ 10^9, −10^7 ≤ a0, a1 ≤ 10^7, 1 ≤ k ≤ 5000$，保证 si 严格递增。
所有测试数据的范围和特点如下表所示： (未标明的以上述所有数据的限制为准)
