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 \mathbin{\&} v[x] \mathbin{\&} v[x+1] \mathbin{\&} \cdots \mathbin{\&} v[y]~. Here, ~\&~ refers to bitwise AND.

Constraints

For all subtasks:

~1 \le N, Q \le 100\,000~

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

~1 \le x \le y \le N~

Subtask 1 [25%]

~1 \le N, Q \le 1\,000~

Subtask 2 [30%]

There will be at most ~75\,000~ 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