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$