Given an integer sequence of length $n$, the elements are indexed as $a_1, a_2, a_3, \dots, a_n$. Initially, all elements are zero. A sequence of modifications or queries is provided in chronological order. Each modification or query is one of the following six types:

• 1 i val: Assign the value $val$ to $a_i$.
• 2 val: Add $val$ to all elements simultaneously.
• 3 val: Multiply all elements by $val$ simultaneously.
• 4 val: Assign the value $val$ to all elements simultaneously.
• 5 i: Query the current value of the $i$-th element $a_i$.
• 6: Query the current sum of all elements.

Input

To avoid large input files, the input is provided in the following format:

The first line contains an integer $n$, representing the length of the sequence. The second line contains an integer $q$, followed by $q$ lines, each providing a modification or query. The format of these operations is consistent with the problem description; please refer to the examples. We refer to these $q$ operations as standard operations.

Following this, an integer $t$ is given, followed by $t$ lines, each containing two positive integers $a_i$ and $b_i$, where the index $i$ ranges from $1$ to $t$.

You are required to perform a total of $t \times q$ operations on the sequence of length $n$ (initially all zeros). The $((i - 1)q + j)$-th operation is the $((a_i + j \cdot b_i) \pmod q + 1)$-th standard operation ($1 \le i \le t$ and $1 \le j \le q$).

Output

Output a single integer representing the cumulative sum of the answers to all queries.

Since the answer can be very large, you are only required to output the result modulo $p = 10^7 + 19$.

Note: If the final cumulative sum $ans$ is less than zero, you should output $((ans \pmod p) + p) \pmod p$.

Examples

Input 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

Output 1

2816930

Subtasks

• Subtask 1 (50 points): $1 \le n \le 500000$, $1 \le q \le 10^5$, $1 \le t \le 5$. All $val$ in the input satisfy $-10^9 \le val \le 10^9$, and all $a_i, b_i$ satisfy $0 \le a_i, b_i \le 10^9$.
• Subtask 2 (50 points): $1 \le n \le 10^9$, $1 \le q \le 10^5$, $1 \le t \le 100$. All $val$ in the input satisfy $-10^9 \le val \le 10^9$, and all $a_i, b_i$ satisfy $0 \le a_i, b_i \le 10^9$.