Operation Sequence Simulation

You are given a sequence \(A\) of length \(n\) with initial values. An automated machine supports the following three operations on \(A\):

• 1 l r k: Set every element in the interval \([l, r]\) to \(k\), i.e. \(A_l = k, A_{l+1} = k, \ldots, A_r = k\).
• 2 x y: Swap the values of \(A_x\) and \(A_y\).
• 3 x: Query the current value of \(A_x\).

A second sequence \(B\) of operations (of length \(m\)) is generated. Define \(\Upsilon(l,r)\) as the sum of the results of all type \(3\) queries when starting from the initial array and executing operations \(B_l, B_{l+1}, \ldots, B_r\) in order. (If there is no type \(3\) operation in that range, we define \(\Upsilon(l,r)=0\).)

You will be given \(q\) queries. Each query contains three integers \(l\), \(r\) and \(p\). For each query, compute and output \[ \left(\sum_{i=l}^{r} \Upsilon(i,p)\right) \mod 2^{32} \]

Note: For every simulation (i.e. applying operations from some starting index \(i\) to \(p\) from \(B\)) the array \(A\) is reinitialized to its original state.

inputFormat

The first line contains three integers \(n, m, q\) --- the length of the sequence \(A\), the number of operations in sequence \(B\), and the number of queries, respectively.

The second line contains \(n\) integers \(A_1, A_2, \ldots, A_n\) --- the initial values of \(A\).

The following \(m\) lines each describe an operation in \(B\) in one of the following formats:

• 1 l r k (set operation)
• 2 x y (swap operation)
• 3 x (query operation)

The next \(q\) lines each contain three integers \(l, r, p\) representing a query.

outputFormat

For each query, output a single line containing one integer: the value of \[ \left(\sum_{i=l}^{r} \Upsilon(i,p)\right) \mod 2^{32} \]

sample

5 4 2
1 2 3 4 5
3 3
1 2 4 10
3 3
2 1 5
1 2 3
2 2 4

23
10