You are locked in a parallel universe and for you to be able to escape you have to answer $Q$ queries on an array named $v$ with $N$ elements. The queries are as follows:

• U x val - Change the value of $v[x]$ to $val$.
• Q x y val - Print $val\mathrm{\&}v[x]\mathrm{\&}v[x+1]\mathrm{\&}\cdots \mathrm{\&}v[y]$. Here, $\mathrm{\&}$ refers to bitwise AND.

Constraints

For all subtasks:

$1\le N,Q\le 100000$

$0\le val\le 2^{32}-1$

$1\le x\le y\le N$

Subtask 1 [25%]

$1\le N,Q\le 1000$

Subtask 2 [30%]

There will be at most $75000$ Q queries.

Subtask 3 [45%]

No additional constraints.

Input Specification

On the first line, you will find $N$ and $Q$.
On the second line, you will find $N$ numbers, where the $i^{\text{th}}$ number is $v[i]$.
On the next $Q$ lines, you will find the queries.

Output Specification

For each Q type query, print each result on a different line.

Sample Input

3 3
5 7 15
Q 1 3 7
U 1 0
Q 1 3 15

Sample Output

5
0