stone

时间限制:10s      空间限制:259MB

题目描述

话说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分钟最多能取多少个石子。


输入格式

第一行正整数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]。


输出格式

有M行,第i行表示第i分钟最多能取多少石子。


样例输入

5
3 2 4 7
3
2 5 2 6 4 9
2 4
1 2
3 5

样例输出

2
5
5
【样例说明】
石子每堆个数分别为0,5,2,5,0。
第1分钟,从第2到第4堆中选2个;
第2分钟,从第1到第2堆中选5个;
第3分钟,从第3到第5堆中选8个,但最多只能选5个。

【数据范围】
100%  N<=40000   M<=N   1<=L[i]<=R[i]<=N   A[i]<=500

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose