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