Interval Operation Simulation

You are given n variables x[1], x[2], ..., x[n] initially set to 0. A list of m operations is provided. There are two types of operations:

• (1, id, v): Add v to x[id].
• (2): Multiply all variables by 2.

All arithmetic is performed modulo \(10^4\). That is, for two numbers a and b, you should compute the operations as follows:

• Addition: \(c = (a + b) \mod 10^4\)
• Subtraction: \(c = (a - b + 10^4) \mod 10^4\)
• Multiplication: \(c = a \times b \mod 10^4\)

The complete sequence of operations to execute is given in q segments. Each segment is represented by an interval \([l_i, r_i]\) (1-indexed), and the final sequence is the concatenation of the operations in these segments in the given order, where within each segment the operations are executed in increasing order of their indices.

Your task is to simulate the operations and output the final values of all n variables.

inputFormat

The input format is as follows:

n m q
op1
op2
... (m operations)
interval1
interval2
... (q intervals)

Each operation is either in the format 1 id v (for type 1) or 2 (for type 2). Each interval is given by two integers l r representing the starting and ending indices (1-indexed) of operations in that segment.

outputFormat

Output n integers separated by a single space. These represent the final values of x[1] to x[n] after executing the entire sequence of operations.

sample

3 5 2
1 1 5
2
1 2 7
1 3 3
2
1 3
4 5

20 14 6