P5358 [SDOI2019] Fast Queries

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.

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 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}$.

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