Description

Given an integer sequence of length $n$, whose elements are numbered in order as $a_1,~a_2,~a_3,~\dots,~a_n$. Initially, all elements are zero. Then, in chronological order, a number of modifications or queries on this sequence are given. Each modification or query must be one of the following six types:

• 1 i val: Assign $a_i$ the given integer $val$.

• 2 val: Add $val$ to all elements at the same time.

• 3 val: Multiply all elements by $val$ at the same time.

• 4 val: Assign all elements to $val$ at the same time.

• 5 i: Query the current value of the $i$-th element $a_i$.

• 6: Query the current sum of all elements.

Input Format

To avoid overly large input, the input file uses the following format.

The first line contains an integer $n$, denoting the length of the sequence.

The second line contains an integer $q$, and then the next $q$ lines each give one modification or query. The input format is the same as described above; see the sample.

We call the above modifications or queries the standard operations.

After that, an integer $t$ is given, and then the next $t$ lines each contain two positive integers $a_i$ and $b_i$, where the index $i$ runs from $1$ to $t$.

You need to perform a total of $t\times q$ operations on the sequence of length $n$ that is initially all zeros.

The $\Big((i-1)q+j\Big)$-th operation is the $\Big((a_i + j b_i) \mod{q} + 1\Big)$-th given standard operation ($1\le i\le t$ and $1\le j\le q$).

Output Format

Output one integer, representing the total sum of all query answers.

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

Note: If the final accumulated sum $\mathrm{ans}$ is negative, you should output $\big((ans \mod{p})+p\big)\mod{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

Hint

Subtask $1$ ($50$ points): $1\le n\le 500000$, $1\le q\le 10^5$, and $1\le t\le 5$. All $val$ appearing in the input satisfy $-10^9\le val\le 10^9$. All $a_i$ and $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$, and $1\le~t~\le~100$. All $val$ appearing in the input satisfy $-10^9\le val\le 10^9$. All $a_i$ and $b_i$ satisfy $0\le a_i,b_i\le 10^9$.

Translated by ChatGPT 5