408361: GYM103107 A And RMQ

You are given a sequence consisting of $$$N$$$ integers $$$\lbrace a_i \rbrace$$$. There will be $$$m$$$ different events.

• $$$\texttt{AND} ~ l ~ r ~ v$$$ – for all elements $$$a_i ~ (l \leq i \leq r)$$$, change $$$a_i$$$ to $$$a_i ~ \& ~ v$$$, where $$$\&$$$ means bitwise AND

• $$$\texttt{UPD} ~ x ~ v$$$ – change $$$a_x$$$ to $$$v$$$

• $$$\texttt{QUE} ~ l ~ r$$$ – ask for the maximum value of $$$a_i$$$ where $$$l \leq i \leq r$$$

Please write a program to support these events efficiently.

The first line contains two integers $$$N, M ~ (1 \leq N, M \leq 400\,000)$$$ denoting the length of sequence and the number of events.

The second line contains $$$N$$$ integers $$$a_1, a_2, \cdots, a_n ~ (1 \leq a_i \leq 2^{30}-1)$$$ denoting the initial elements of the sequence.

For the next $$$M$$$ lines, each line describes an event. It is guaranteed that $$$1 \leq l, r, x \leq n$$$ and $$$1 \leq v \leq 2^{30}-1$$$.

For each $$$\texttt{QUE}$$$ event, print a single line containing an integer, denoting the answer.

It is guaranteed that there is at least one $$$\texttt{QUE}$$$ event.

5 11
6 3 5 2 3
AND 2 4 10
UPD 1 8
AND 3 4 7
UPD 1 6
QUE 1 4
AND 3 5 10
AND 3 5 2
UPD 5 1
QUE 2 5
UPD 3 6
QUE 1 5

6
2
6

Since the input file is large, please use 'fread' (strongly recommended) or 'scanf' instead of 'cin'.