Machine Operations on Array

You are given an array \(a[1 \ldots n]\) initially filled with zeros. There are \(m\) machines placed from left to right. The \(i\)-th machine is of type \(o_i\) and has two parameters \(x_i\) and \(y_i\). The machine operations are defined as follows:

• If \(o_i = 1\), then the machine adds \(y_i\) to the element \(a_{x_i}\). It is guaranteed that \(1 \le x_i \le n\) and \(1 \le y_i \le 10^4\).
• If \(o_i = 2\), then the machine executes the operations of machines \(x_i, x_i+1, \ldots, y_i\) exactly once each. It is guaranteed that \(1 \le x_i \le y_i \le i-1\).

It is further guaranteed that \(o_1 = 1\).

After setting up the machines, you are given a sequence of \(k\) machine indices \(c_1, c_2, \ldots, c_k\). You must execute the operations of these machines, one by one in the given order. Note that if a machine of type 2 is executed, it will in turn execute the operations of several other machines (which may themselves be type 2, causing nested executions).

Your task is to determine the final state of the array \(a[1\ldots n]\) modulo \(10007\); that is, for each valid index \(i\), output \(a_i \bmod 10007\).

Note: The operations of a machine are always executed independently. That is, if a machine is executed multiple times (either directly or indirectly), its effect will be applied each time.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) separated by spaces, representing the size of the array, the number of machines, and the number of operations to execute, respectively.

The next \(m\) lines contain three integers each: \(o_i\), \(x_i\) and \(y_i\), describing the \(i\)-th machine.

The last line contains \(k\) integers \(c_1, c_2, \ldots, c_k\) separated by spaces, representing the indices of the machines whose operations are executed (in the given order).

outputFormat

Output a single line containing \(n\) integers. The \(i\)-th integer should be the final value of \(a_i\) modulo \(10007\) after all operations have been performed.

sample

3 2 1
1 2 5
2 1 1
1

0 5 0