P14188 [ICPC 2024 Hangzhou R] Barkley III

There are $n$ little pigs in Pigeland. All of them are proficient in competitive programming, and the $i$-th of them has $a_i$ rating. If $k$ pigs $p_1, p_2, \cdots, p_k$ form a team, the rating of the team will be $a_{p_1}\ \&\ a_{p_2}\ \&\ a_{p_3}\ \& \cdots \&\ a_{p_k}$, where $\&$ denotes the bitwise AND operation. There are some programming contests to take place. Pigeland can send exactly one team to participate in each contest. For the $i$-th competition, only the pigs numbered between $l_i$ and $r_i$ (both inclusive) have time to participate. Unfortunately, due to a shortage of funds, exactly one pig numbered between $l_i$ and $r_i$ has to be removed. Meanwhile, all other pigs in the interval will participate in the contest. Pig-head, the coach of Pigeland, needs to properly select pigs who will not participate so that the team's rating is maximized. However, through training and participating in contests, the rating of pigs may be changed. As Pig-head's best friend, your task is to maintain the pigs' rating for the following $q$ events belonging to three types. - $1 \; l \; r \; x$: Pig-head changes the rating of each pig numbered between $l$ and $r$ (both inclusive) by executing the bitwise AND operation with $x$. More formally, for all $l \le i \le r$, $a_i$ becomes $a_i\ \&\ x$. - $2 \; s \; x$: Pig-head changes the rating of the $s$-th pig to $x$. - $3 \; l \; r$: Pig-head asks for the maximum rating when forming a team by selecting pigs numbered between $l$ and $r$ (both inclusive) and removing exactly one of them.

There is only one test case in each test file. The first line contains two integers $n$ and $q$ ($2 \le n \le 10^6$, $1 \le q \le 10^6$) indicating the number of pigs and the number of events. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{63}$) where $a_i$ indicates the rating of the $i$-th pig. For the following $q$ lines, the $i$-th line first contains an integer $op_i$ ($op_i \in \{1, 2, 3\}$) indicating the type of the $i$-th event. If $op_i = 1$, then three integers $l$, $r$, and $x$ follow ($1 \le l \le r \le n$, $0 \le x < 2^{63}$); If $op_i = 2$, then two integers $s$ and $x$ follow ($1 \le s \le n$, $0 \le x < 2^{63}$); If $op_i = 3$, then two integers $l$ and $r$ follow ($1 \le l < r \le n$).

For each event of the third type, output one line containing one integer indicating the maximum rating of the team.