题目描述

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

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

现在小可爱依次执行了机器 $c_1, c_2, ..., c_k$ 的操作，想知道最后得到的数组是什么。由于数组中的元素可能很大，你只需要帮她求出每个元素除以 $10007$ 的余数即可。

输入格式

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

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

接下来 $m$ 行，每行三个正整数，第一个正整数 $o_i ∈ \{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$ 的余数。

样例

输入

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

输出

8 0

解释

先执行第一个机器的操作，给 $a_1$ 加上了 $2$。 然后执行第二个机器的操作，它操作了第一个机器，给 $a_1$ 加上了 $2$。 然后执行第三个机器的操作，它先操作了第一个机器，给 $a_1$ 加上了 $2$，然后操作了第二个机器。第二个机器又操作了第一个机器，给 $a_1$ 加上了 $2$。 所以最后 $a_1 = 8, a_2 = 0$。

数据规模与约定

• 对于 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$。