cstdio
mikumikumi
cstdio【试题来源】
2011中国国家集训队命题答辩
【问题描述】
话说Nan在海边等人，预计还要等上M分钟。为了打发时间，他玩起了石子。
Nan搬来了N堆石子，编号为1到N，每堆包含Ai颗石子。
每1分钟，Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海（好疼的玩法），如果[Li,Ri]剩下石子不够Ki颗，则取尽量地多。
为了保留扔石子的新鲜感，Nan保证任意两个区间[Li,Ri]和[Lj,Rj] ，不会存在Li<=Lj & Rj<=Ri的情况，即任意两段区间不存在包含关系。
可是，如果选择不当，可能无法扔出最多的石子，这时NN就会不高兴了。所以他希望制定一个计划，他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。
现在他想你告诉他，在满足前i-1分钟都取到你回答的颗数的情况下，第i分钟最多能取多少个石子。
Nan搬来了N堆石子，编号为1到N，每堆包含Ai颗石子。
每1分钟，Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海（好疼的玩法），如果[Li,Ri]剩下石子不够Ki颗，则取尽量地多。
为了保留扔石子的新鲜感，Nan保证任意两个区间[Li,Ri]和[Lj,Rj] ，不会存在Li<=Lj & Rj<=Ri的情况，即任意两段区间不存在包含关系。
可是，如果选择不当，可能无法扔出最多的石子，这时NN就会不高兴了。所以他希望制定一个计划，他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。
现在他想你告诉他，在满足前i-1分钟都取到你回答的颗数的情况下，第i分钟最多能取多少个石子。
【输入格式】
第一行正整数N，表示石子的堆数；
第二行正整数x,y,z,P，(1<=x,y,z<=N;P<=500)
有等式A[i]=[(i-x)^2+(i-y)^2+(i-z)^2] mod P；
第三行正整数M，表示有M分钟；
第四行正整数K[1],K[2],x,y,z,P，(x,y,z<=1000;P<=10000)
有等式K[i]=(x*K[i-1]+y*K[i-2]+z)mod P。
接下来M行，每行两个正整数L[i],R[i]。
第二行正整数x,y,z,P，(1<=x,y,z<=N;P<=500)
有等式A[i]=[(i-x)^2+(i-y)^2+(i-z)^2] mod P；
第三行正整数M，表示有M分钟；
第四行正整数K[1],K[2],x,y,z,P，(x,y,z<=1000;P<=10000)
有等式K[i]=(x*K[i-1]+y*K[i-2]+z)mod P。
接下来M行，每行两个正整数L[i],R[i]。
【输出格式】
有M行，第i行表示第i分钟最多能取多少石子。
【样例输入】
5
3 2 4 7
3
2 5 2 6 4 9
2 4
1 2
3 5
3 2 4 7
3
2 5 2 6 4 9
2 4
1 2
3 5
【样例输出】
2
5
5
5
5
【样例说明】
石子每堆个数分别为0,5,2,5,0。
第1分钟，从第2到第4堆中选2个；
第2分钟，从第1到第2堆中选5个；
第3分钟，从第3到第5堆中选8个，但最多只能选5个。
第1分钟，从第2到第4堆中选2个；
第2分钟，从第1到第2堆中选5个；
第3分钟，从第3到第5堆中选8个，但最多只能选5个。
【数据规模和约定】
20% N<=10
50% N<=2000
100% N<=40000 M<=N 1<=L[i]<=R[i]<=N A[i]<=500
50% N<=2000
100% N<=40000 M<=N 1<=L[i]<=R[i]<=N A[i]<=500