You are given an array \(A\), consisting of \(N\) integers \(A_1, A_2, ..., A_N\).

You will be asked queries of following \(3\) types:

\(1 \space L \space R \space X :\) update all the elements in the range \(L\) to \(R\) to \(X\), i.e. do assign operation \(A_i = X\) , \(L \le i \le R\)
\(2 \space L \space R \space X :\) change all the elements in the range \(L\) to \(R\) to \(A_i \newcommand*\xor{\oplus} X\), i.e. do Bitwise XOR operation \(A_i = A_i \newcommand*\xor{\oplus} X\), \(L \le i \le R\) (where \(\newcommand*\xor{\oplus}\) denotes the Bitwise XOR operator).
\(3 \space L \space R :\) output the sum of range \(L\) to \(R\), i.e. \(\sum_{i = L}^R{A_i} = A_L + A_{L + 1} + .... + A_R \)

Note: Since the size of the input and output is large, please use fast I/O and memory accordingly.

Input format

The first line of input contains an integer \(N\).
The second line of input contains \(N\) space-separated integers \(A_1, A_2, ..., A_N\).
The third line of input contains an integer \(Q\).
Next \(Q\) lines first contains an integer \(T_i\) which denotes the type of the query. If \(T_i = 1 \space or \space 2\) then next followed three space-separated integers \( L \space R \space X\) otherwise if \(T_i = 3\) then next followed two space-separated integers \(L \space R\).

It is guaranteed that there will be at least one query of type \(3\).

Output format

For each query of type \(3\), print a single integer denoting the answer to that query.

Constraints

\(1 \le N, Q \le 2 * 10^5 \\ 0 \le A_i, X< 2^{10} \\ 1 \le T_i \le 3 \\ 1 \le L \le R \le N\)