题目描述

小可可有一个数组 $\{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$ 的余数即可。

输入格式

第一行三个正整数 $n,m,k$。

接下来一行 $k$ 个正整数 $\{c_k\}$。

接下来 $m$ 行，第 $i$ 行三个正整数 $o_i,x_i,y_i$。

输出格式

一行 $n$ 个非负整数，表示数组 $\{a_n\}$ 中每个元素的值除以 $10007$ 的余数。

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

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\%$ 的数据，$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 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$。