小可可有一个长度为 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 的余数。

样例 1 解释

先执行第一个机器的操作，给 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。