测试数据来自 system/2051
描述
给定一个长度为 n 的整数数列,里面的元素依次编号为 a1,a2,a3,⋯,an。初始的时候,所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问,每一次修改或询问一定为以下六种情况之一:
- 1 i val :将 ai 赋值为给定整数 val;
- 2 val :将所有元素同时加上 val;
- 3 val :将所有元素同时乘上 val;
- 4 val :将所有元素同时赋值为 val;
- 5 i :询问第 i 个元素 ai 现在的值是多少;
- 6 :询问现在所有元素的和。
格式
输入格式
为了避免读入太大,输入文件采取如下的形式。
第一行给定整数 n,表示给定数列长度为n。
第二行给定整数 q,并且之后的 q 行,每一行提供一个修改或询问,输入的格式与题目所述一致,请参见样例。
我们称上述给定的修改或询问为标准操作。
之后给定一个整数t,并且之后的t行每行给定两个正整数ai和bi,这里的下标i依次记为1到t。
你需要对初始值全为零的长度为n的序列做总计 t×q 次操作。
其中第 ((i−1)q+j) 次操作形如第 ((ai+jbi)modq+1) 个给定的标准操作(1≤i≤t且1≤j≤q)。
输出格式
输出一个整数,表示所有询问答案的累计和。
因为答案可能很大,只要求输出其结果关于 p=107+19 取模后的值。
注意:若最终的累计和 ans 小于零,你应该输出 ((ansmodp)+p)modp)。
样例1
样例输入1
样例输出1
限制
数据规模
子任务1:(50分)1≤n≤500000,1≤q≤105 且 1≤t≤5,所有在输入中出现的val 满足−109≤val≤109,所有ai和bi满足0≤ai,bi≤109
子任务2:(50分)1≤n≤109,1≤q≤105 且 1≤t≤100,所有在输入中出现的val 满足−109≤val≤109,所有ai和bi满足0≤ai,bi≤109
时限
2s
内存限制
默认