Automation of Array Operations

You are given an initial array \(A\) of length \(n\), where each element has an initial value. An automation machine supports the following three kinds of operations on \(A\):

• \(\colorbox{f0f0f0}{\texttt{1 x k}}\): update \(A_x\) to \(k\).
• \(\colorbox{f0f0f0}{\texttt{2 x y}}\): swap \(A_x\) and \(A_y\).
• \(\colorbox{f0f0f0}{\texttt{3 x}}\): query the value of \(A_x\).

To test the efficiency of the automation, a sequence \(B\) of length \(m\) has been generated. Each element in \(B\) is one of the operations described above. You will be given \(q\) independent tests. In each test, you are provided with a pair \((l, r)\) which means you need to simulate the operations \(B_l, B_{l+1}, \ldots, B_r\) in order using the initial array \(A\). Note that after each test, the array \(A\) is reset to its initial values.

Your task is to compute, for each test, the sum of the results of all query operations (i.e. type 3 operations) performed during that test, modulo \(2^{32}\) (i.e. an unsigned 32-bit integer overflow).

inputFormat

The first line contains three integers \(n, m, q\) representing the length of the initial array, the number of operations in sequence \(B\), and the number of tests, respectively.

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

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

• 1 x k: update operation (set \(A_x = k\)).
• 2 x y: swap operation (swap \(A_x\) and \(A_y\)).
• 3 x: query operation (output the value of \(A_x\)).

The next \(q\) lines each contain two integers \(l\) and \(r\) representing a test: simulate the operations \(B_l, B_{l+1}, \ldots, B_r\) in order.

outputFormat

For each test, output a single integer on a separate line – the sum of the results from all query operations (type 3) modulo \(2^{32}\).

sample

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

2
15
17