【CZYZOI 2017.04.16 A】 数列

内存限制: 128 MiB 时间限制: 1000 ms
标准输入输出

题目描述

Czy手上有一个长度为 nn 的数列,第i个数为 xix_i

他现在想知道,对于给定的 a,b,ca,b,c ,他要找到一个 ii ,使得 a(i+1)xi2+(b+1)ixi+(c+i)=0a*(i+1)*x_i^2+(b+1)*i*x_i+(c+i)=0 成立。

如果有多个 ii 满足,Czy想要最小的那个 ii

Czy有很多很多组询问需要你回答,多到他自己也不确定有多少组。所以在输入数据中 a=b=c=0a=b=c=0 标志着Czy的提问的结束。

更加糟糕的是,Czy为了加大难度,决定对数据进行加密以防止离线算法的出现。

假设你在输入文件中读到的三个数为 a0,b0,c0a_0,b_0,c_0 ,那么Czy真正要询问的 a=a0+LastAns,b=b0+LastAns,c=c0+LastAnsa=a_0+LastAns,b=b_0+LastAns,c=c_0+LastAns .

LastAnsLastAns 的值是你对Czy的前一个询问的回答。如果这是第一个询问,那么 LastAns=0LastAns=0

所有的询问都将会按上述方式进行加密,包括标志着询问的结束的那个询问也是这样。

输入格式

输入文件第一行包含一个整数 nn ,表示数列的长度。

输入文件第二行包含 nn 个整数,第 ii 个数表示 xix_i 的值。

接下来若干行,每行三个数,表示加密后的 a,b,ca,b,c 值(也就是上文所述的 a0,b0,c0a_0,b_0,c_0

输出格式

包含若干行,第 ii 行的值是输入文件中第 ii 个询问的答案。注意,你不需要对标志着询问结束的那个询问作答。

同时,标志着询问结束的询问一定是输入文件的最后一行。也就是,输入文件不会有多余的内容。

样例

输入样例

5
-2 3 1 -5 2
-5 -4 145
-1 -6 -509
-9 -14 40
-3 -13 21
-3 -3 -3

输出样例

5
4
3
3

数据范围与提示

对于 40%40\% 的数据,满足 N1000N\le 1000 ,需要作出回答的询问个数不超过 10001000 .

对于100%100\% 的数据,满足 N50000N\le50000 ,需要作出回答的询问个数不超过 500000500000 .

xix_i 的绝对值不超过 3000030000 ,解密后的 aa 的绝对值不超过 5000050000,解密后的 bb 的绝对值不超过 10810^8 ,解密后的 cc 的绝对值不超过 101810^{18}.