小可可有一个长度为 $n$ 的初始都为 $0$ 的数组和从左到右的 $m$ 个机器，每个机器 $i$ 都有两种类别之一。若机器 $i$ 是第一种机器，那么它需要执行的操作是将 $a_{x_i}$ 的值加上 $y_i$；如果机器 $i$ 是第二种机器，那么它需要执行的操作是依次执行第 $l_i$ 到第 $r_i$ 个机器的操作，其中有 $r_i< i$。

需要注意的是，每个第二种机器只会执行它左边机器的操作。

现在小可可依次执行了机器 $c_1, c_2, \cdots , c_k$ 的操作，想知道最后得到的数组是什么。

由于数组中的元素可能很大，你只需要帮她求出每个元素除以 $10007$ 的余数即可。

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

接下来一行 $k$ 个正整数，表示序列 $c$。

接下来 $m$ 行，每行三个正整数，第一个正整数 $o_i\in \{1,2\}$，表示机器 $i$ 的类型。

如果 $o= 1$，则接下来两个正整数 $x_i, y_i,\ 1≤x_i≤n,\ 1≤y_i≤10^4$。

如果 $o= 2$，则接下来两个正整数 $l_i, r_i,\ 1≤l_i≤r_i< i$。

一行 $n$ 个正整数，表示数组中每个元素除以 $10007$ 的余数。

对于 10% 的数据，$1≤n, m, k≤10$。
对于 30% 的数据，$1≤n, m, k≤1000$。
对于另 20% 的数据，$n= 1$。
对于另 20% 的数据，$k= 1$。
对于 100% 的数据，$1≤n, m, k≤2×10^5$。

8 0

先执行第一个机器的操作，给 $a_1$ 加上了 2。

然后执行第二个机器的操作，它操作了第一个机器，给 $a_1$ 加上了 2。

然后执行第三个机器的操作，它先操作了第一个机器，给 $a_1$ 加上了 2，然后操作了第二个机器。第二个机器又操作了第一个机器，给 $a_1$ 加上了 2。

所以最后 $a_1= 8, a_2= 0$。