描述

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

• 1 i val ：将 \(a_i\) 赋值为给定整数 \(val\)；
• 2 val ：将所有元素同时加上 \(val\)；
• 3 val ：将所有元素同时乘上 \(val\)；
• 4 val ：将所有元素同时赋值为 \(val\)；
• 5 i ：询问第 \(i\) 个元素 \(a_i\) 现在的值是多少；
• 6 ：询问现在所有元素的和。

格式

输入格式

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

第一行给定整数 \(n\)，表示给定数列长度为\(n\)。
第二行给定整数 \(q\)，并且之后的 \(q\) 行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。
我们称上述给定的修改或询问为标准操作。
之后给定一个整数\(t\)，并且之后的\(t\)行每行给定两个正整数\(a_i\)和\(b_i\)，这里的下标\(i\)依次记为\(1\)到\(t\)。

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

输出格式

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

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

注意：若最终的累计和 \(ans\) 小于零，你应该输出 \(\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

限制

数据规模

子任务\(1\)：（\(50\)分）\(1\le n\le 500000\)，\(1\le q\le 10^5\) 且 \(1\le t\le 5\)，所有在输入中出现的\(val\) 满足\(-10^9\le val\le 10^9\)，所有\(a_i\)和\(b_i\)满足\(0\le a_i,b_i\le 10^9\)

子任务\(2\)：（\(50\)分）\(1\le n\le 10^9\)，\(1\le q\le 10^5\) 且 \(1\le t\le 100\)，所有在输入中出现的\(val\) 满足\(-10^9\le val\le 10^9\)，所有\(a_i\)和\(b_i\)满足\(0\le a_i,b_i\le 10^9\)

时限

2s

内存限制

默认