小可可有一个数组 $\{a_n\}$（初始值为 $\{a_n\}=\{0,0,\ldots,0\}$）和从左到右的 $m$ 个机器，其中第 $i$ 个机器有类别 $o_i \in \{1,2\}$ 和参数 $x_i,y_i$。第 $i$ 个机器执行的操作如下：
- 若 $o_i=1$，则将 $a_{(x_i)}$ 加上 $y_i$，此时保证 $1 \le x_i \le n$，$1 \le y_i \le 10^4$。
- 若 $o_i=2$，则执行第 $x_i \sim y_i$ 个机器的操作各一次，此时保证 $1 \le x_i \le y_i \le i-1$。
- 特别地，保证 $o_1=1$。
现在，小可可依次执行了第 $c_1,c_2,\ldots,c_k$ 个机器的操作各一次，她想知道最后得到的数组 $\{a_n\}$ 是什么。
由于数组中元素的值可能很大，你只需要帮她求出每个元素除以 $10007$ 的余数即可。
## Input
第一行三个正整数 $n,m,k$。
接下来一行 $k$ 个正整数 $\{c_k\}$。
接下来 $m$ 行，第 $i$ 行三个正整数 $o_i,x_i,y_i$。
## Output
一行 $n$ 个非负整数，表示数组 $\{a_n\}$ 中每个元素的值除以 $10007$ 的余数。
[samples]
## Background
**本题的数据不是官方数据。**
**本题征集（能够上传到这里的）官方数据。**
**（没法上传到这里的）官方数据：<https://www.luogu.com.cn/training/499869>**
**本题民间数据下载：<http://8.136.99.126/blog/3/67f0c2307aadac7b413b837b>**
## Note
### 样例 1 解释
先执行第 $1$ 个机器的操作，给 $a_1$ 加上了 $2$。
然后执行第 $2$ 个机器的操作，它操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。
然后执行第 $3$ 个机器的操作。它先操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$；然后操作了第 $2$ 个机器，第 $2$ 个机器又操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。
综上所述，最后得到的数组为 $\{8,0\}$。
### 数据范围
对于 $10\%$ 的数据，$n,m,k \le 10$。
对于 $30\%$ 的数据，$n,m,k \le 1000$。
对于另外 $20\%$ 的数据，$n=1$。
对于另外 $20\%$ 的数据，$k=1$。
对于 $100\%$ 的数据，$1 \le n,m,k \le 2 \times 10^5$，$1 \le c_i \le m$，$o_i \in \{1,2\}$，$o_1=1$。此外，对于第 $i$ 个机器，保证：
- 若 $o_i=1$，则 $1 \le x_i \le n$，$1 \le y_i \le 10^4$。
- 若 $o_i=2$，则 $1 \le x_i \le y_i \le i-1$。