P10374 [AHOI2024 Junior / USTC Guochuang Cup Junior 2024] Operations

**The testdata for this problem is not official.** **Official testdata (that can be uploaded here) is being collected.** **Official testdata (that cannot be uploaded here): ** **Unofficial testdata download: **

Xiaokeke has an array $\{a_n\}$ (initially $\{a_n\}=\{0,0,\ldots,0\}$) and $m$ machines arranged from left to right. For the $i$-th machine, its type is $o_i \in \{1,2\}$ and its parameters are $x_i,y_i$. The operation performed by the $i$-th machine is as follows: - If $o_i=1$, add $y_i$ to $a_{(x_i)}$. It is guaranteed that $1 \le x_i \le n$ and $1 \le y_i \le 10^4$. - If $o_i=2$, perform the operations of machines $x_i \sim y_i$ once each. It is guaranteed that $1 \le x_i \le y_i \le i-1$. - In particular, it is guaranteed that $o_1=1$. Now Xiaokeke executes the operations of machines $c_1,c_2,\ldots,c_k$ once each in order. She wants to know what the final array $\{a_n\}$ is. Since the values in the array may be very large, you only need to output the remainder of each element modulo $10007$.

The first line contains three positive integers $n,m,k$. The next line contains $k$ positive integers $\{c_k\}$. The next $m$ lines each contain three positive integers $o_i,x_i,y_i$ on the $i$-th line.

Output one line with $n$ non-negative integers, representing the remainder of each element in $\{a_n\}$ modulo $10007$.

### Sample 1 Explanation First, execute the operation of machine $1$, which adds $2$ to $a_1$. Then execute the operation of machine $2$. It operates machine $1$, adding $2$ to $a_1$. Then execute the operation of machine $3$. It first operates machine $1$, adding $2$ to $a_1$; then it operates machine $2$, and machine $2$ operates machine $1$ again, adding $2$ to $a_1$. In summary, the final array is $\{8,0\}$. ### Constraints For $10\%$ of the testdata, $n,m,k \le 10$. For $30\%$ of the testdata, $n,m,k \le 1000$. For another $20\%$ of the testdata, $n=1$. For another $20\%$ of the testdata, $k=1$. For $100\%$ of the testdata, $1 \le n,m,k \le 2 \times 10^5$, $1 \le c_i \le m$, $o_i \in \{1,2\}$, and $o_1=1$. In addition, for the $i$-th machine, it is guaranteed that: - If $o_i=1$, then $1 \le x_i \le n$ and $1 \le y_i \le 10^4$. - If $o_i=2$, then $1 \le x_i \le y_i \le i-1$. Translated by ChatGPT 5