题目描述

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

• $1\ i\ \text{val}$：将 $a_i$ 赋值为给定整数 $\text{val}$；
• $2\ \text{val}$：将所有元素同时加上 $\text{val}$；
• $3\ \text{val}$：将所有元素同时乘上 $\text{val}$；
• $4\ \text{val}$：将所有元素同时赋值为 $\text{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) \bmod q + 1\big)$ 个给定的标准操作（$1 \le i \le t$ 且 $1 \le j \le q$）。

输出格式

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

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

注意：若最终的累计和 $\text{ans}$ 小于零，你应该输出 $\big((\text{ans} \bmod p) + p\big) \bmod p$。

样例

输入

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

输出

2816930

数据范围与提示

• 子任务 1（$50$ 分）：
  $1 \le n \le 500000$，$1 \le q \le 10^5$ 且 $1 \le t \le 5$，所有在输入中出现的 $\text{val}$ 满足 $-10^9 \le \text{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$，所有在输入中出现的 $\text{val}$ 满足 $-10^9 \le \text{val} \le 10^9$，所有 $a_i$ 和 $b_i$ 满足 $0 \le a_i, b_i \le 10^9$。