Background

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): https://www.luogu.com.cn/training/499869

Unofficial testdata download: https://scg3.piaoztsdy.cn/training/69bce235a7cf509104565c83

Problem Description

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

Input Format

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 Format

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

2 3 3
1 2 3
1 1 2
2 1 1
2 1 2

8 0

Hint

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