题目描述
sosusosu 虐爆 OI 之后成为了一名文化课选手。一天,他做作业碰到了一堆数列问题,每道题给出的数列都是以下形式:
给定一个下标从 0 开始,无限长的整数列 {ai}, i∈N,已知 a0,a1 的值,以及递推式 ai+2=kai+1+ai, 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 中,使得 asi 最大的 si 和使得 asi 最小的 si 的值。如果这样的 si 有多个,请你回答最小的一个。
样例 1
8
1 2 3 4 5 6 7 8
2
10 -6 1
0 0 1
2 1
1 1
第一个数列的前 9 项分别为 10,−6,4,−2,2,0,2,2,4,使得 asi 最大的 si 为 2 和 8(a2=a8=4)其中 2 较小,使得 asi 最小的 si 为 1(a1=−6)。
第二个数列每项都等于 0,因此 S 中的每个元素 si 都既使 asi 最大也使 asi 最小,故答案是 S 中最小元素。
3
0 1 2
2
-2 3 1
3 -2 2
1 0
0 1
第一个数列的前 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)。
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
536870912 2
2 536870912
536870912 16
8 536870912
见附加文件(在页面上方下载)。其中除了前 3 个样例外还有约定分别和测试点 1, 9, 14 相同的样例各一个。
数据范围与提示
对于所有数据,1≤n≤3×105,1≤m≤105,0≤si≤109,−107≤a0,a1≤107,1≤k≤5×103,保证 si 严格单调递增。
注意,本题输入规模较大,请使用较快的方式读入。LOJ 上 C 语言的 scanf
、C++ 的关闭同步的 cin
、Pascal 的 read
读入此题数据时间均在 50 ~ 200 毫秒之间。
所有测试数据的范围和特点如下表所示:
(未标明的以上述所有数据的限制为准)
测试点编号 |
n,m 的限制 |
a0,a1,k 的范围 |
特殊限制 |
1 |
n,m≤100 |
−100≤a0,a1≤100,k≤10 |
sm≤10 |
2 |
3 |
4 |
n≤105 |
k=1 |
- |
5 |
6 |
7 |
- |
a0⋅a1≥0(即 a0,a1 不会一正一负) |
8 |
∣a1∣≥∣a0∣ |
9 |
S 中元素都是偶数 |
10 |
11 |
12 |
k≤10 |
13 |
k≤100 |
14 |
k≤1000 |
- |
15 |
- |
16 |
n≤1.5×105 |
k≤10 |
17 |
n≤2×105 |
k≤100 |
18 |
n≤2.5×105 |
k≤1000 |
19 |
- |
20 |