Description

Czy手上有一个长度为n的数列，第i个数为xi。

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

如果有多个i满足，Czy想要最小的那个i。

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

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

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

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

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

Input

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

输入文件第二行包含n个整数，第i个数表示xi的值。

接下来若干行，每行三个数，表示加密后的a,b,c值（也就是上文所述的a0,b0,c0）

Output

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

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

Sample Input

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

Sample Output

5433

HINT

【数据范围】

对于40%的数据，满足N<=1000，需要作出回答的询问个数不超过1000.

对于100%的数据，满足N<=50000，需要作出回答的询问个数不超过500000，xi的绝对值不超过30000，解密后的a的绝对值不超过50000，解密后的b的绝对值不超过10^8，解密后的c的绝对值不超过10^18.

——————————————————————————————————————————————————————————————————

Solution

首先吐槽一下出题人，题目说了，这是一道不允许离线算法的题，然而，std却是离线算法，那么到底是什么离线算法呢？待我慢慢道来。

仔细看题，发现输入文件最后一行有玄机。由“所以在输入数据中a=b=c=0标志着Czy的提问的结束。”知道，输入文件的最后一行应该是（a0,b0,c0）而a0+lastans=a（a才是要询问的，且a=0）b、c以此类推。所以lastans=-a0

机智的读者可能已经看出我的意思：输入文件的最后一行竟然暗示了倒数第二行的ans！

由“a*(i+1)*xi2+(b+1)*i*xi+(c+i)=0”知，我们把i=刚刚求出来的lastans代入，又根据a=a0+lastans，可以把方程化为一个关于lastans的一元一次方程，然后把lastans解出来，再往前面代入就可以了。

最后赞一下出题人。^-^