[AHOI2024 初中组] 操作
题目描述
小可可有一个长度为 $n$ 的,初始都为 $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$ 个机器的操作各一次,她想知道最后得到的数组是什么。
由于数组中元素的值可能很大,你只需要帮她求出每个元素除以 $10007$ 的余数即可。
输入输出格式
输入格式
第一行三个正整数 $n,m,k$。
接下来一行 $k$ 个正整数 $\{c_k\}$。
接下来 $m$ 行,第 $i$ 行三个正整数 $o_i,x_i,y_i$。
输出格式
一行 $n$ 个非负整数,表示数组 $\{a_n\}$ 中每个元素的值除以 $10007$ 的余数。
输入输出样例
输入样例 #1
2 3 3
1 2 3
1 1 2
2 1 1
2 1 2
输出样例 #1
8 0
说明
### 样例 1 解释
先执行第 $1$ 个机器的操作,给 $a_1$ 加上了 $2$。
然后执行第 $2$ 个机器的操作,它操作了第 $1$ 个机器,给 $a_1$ 加上了 $2$。
然后执行第 $3$ 个机器的操作。它先操作了第 $1$ 个机器,给 $a_1$ 加上了 $2$;然后操作了第 $2$ 个机器,第 $2$ 个机器又操作了第 $1$ 个机器,给 $a_1$ 加上了 $2$。
综上所述,最后得到的数组为 $\{8,0\}$。
### 数据范围
对于 $10\%$ 的数据,$1 \le n,m,k \le 10$。
对于 $30\%$ 的数据,$1 \le 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 n$,$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$。