快速查询

快速查询

测试数据来自 system/2051

描述

给定一个长度为 nn 的整数数列,里面的元素依次编号为 a1,a2,a3,,ana_1,a_2,a_3,\cdots,a_n。初始的时候,所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问,每一次修改或询问一定为以下六种情况之一:

  • 1 i val :将 aia_i 赋值为给定整数 valval
  • 2 val :将所有元素同时加上 valval
  • 3 val :将所有元素同时乘上 valval
  • 4 val :将所有元素同时赋值为 valval
  • 5 i :询问第 ii 个元素 aia_i 现在的值是多少;
  • 6 :询问现在所有元素的和。

格式

输入格式

为了避免读入太大,输入文件采取如下的形式。

第一行给定整数 nn,表示给定数列长度为nn
第二行给定整数 qq,并且之后的 qq 行,每一行提供一个修改或询问,输入的格式与题目所述一致,请参见样例。
我们称上述给定的修改或询问为标准操作。
之后给定一个整数tt,并且之后的tt行每行给定两个正整数aia_ibib_i,这里的下标ii依次记为11tt

你需要对初始值全为零的长度为nn的序列做总计 t×qt\times q 次操作。
其中第 ((i1)q+j)\Big((i-1)q+j\Big) 次操作形如第 ((ai+jbi)mod  q+1)\Big((a_i + j b_i) \mod{q} + 1\Big) 个给定的标准操作(1it1\le i\le t1jq1\le j\le q)。

输出格式

输出一个整数,表示所有询问答案的累计和。

因为答案可能很大,只要求输出其结果关于 p=107+19p=10^7+19 取模后的值。

注意:若最终的累计和 ansans 小于零,你应该输出 ((ansmod  p)+p)mod  p)\big((ans \mod{p})+p\big)\mod{p})

样例1

样例输入1

7
28
6
4 -192321079
3 418379342
1 3 189801569
3 -840249197
4 -751917965
3 649799919
1 5 -92666141
6
4 451258008
5 1
4 696880327
3 772574465
6
4 301010289
3 480168068
5 3
5 2
4 840536237
5 5
5 4
1 7 -792284106
2 604521872
3 966540578
2 -381646699
3 -939378260
2 -20129935
6
2
0 1
197 199

样例输出1

2816930

限制

数据规模

子任务11:(5050分)1n5000001\le n\le 5000001q1051\le q\le 10^51t51\le t\le 5,所有在输入中出现的valval 满足109val109-10^9\le val\le 10^9,所有aia_ibib_i满足0ai,bi1090\le a_i,b_i\le 10^9

子任务22:(5050分)1n1091\le n\le 10^91q1051\le q\le 10^51t1001\le t\le 100,所有在输入中出现的valval 满足109val109-10^9\le val\le 10^9,所有aia_ibib_i满足0ai,bi1090\le a_i,b_i\le 10^9

时限

2s

内存限制

默认

信息

ID
1100
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者