Given an array a of size \(2^n\) indexed from 0 to \(2^n - 1\) and q queries of type:
\(1 \; l \; r\) (\(0 \le l \le r < 2^n\)): Print \(\max(a_l, a_{l+1}, \dots , a_r)\).
\(2 \; l \; r \; v\) (\(0 \le l \le r < 2^n, 0 \le v \le 10^9\)): Assign value v to every \(a_i\) (\(l \le i \le r\)).
\(3 \; k\) (\(0 \le k < 2^n\)): Permute array a by permutation p, \(p_i = i \; XOR \; k\). Because \(0 \le k < 2^n\) it can be proved that p is a permutation.
If we permute array s by permutation p then the resulting array v will satisfy the condition that \(v_{p_i} = s_i\).
\(\textbf{Input}\)
The first line contains numbers n (\(0 \le n \le 18\)) and q (\(1 \le q \le 2^{18}\)).
The second line contains \(2^n\) numbers - \(a_0, a_1, \dots , a_{2^n - 1}\) (\(0 \le a_i \le 10^9\)) separated by space.
Each of the next q lines contains one type of query from the above mentioned types of queries.
\(\textbf{Output}\)
For each query of first type, output a line containing the answer in chronological order.
For first query the answer is \(\max(1,2,3) = 3\).
After the second query the array is \((0,1,1,1)\).
After third query the array is \((1,0,1,1)\).
At fourth query the answer is \(\max(0,1) = 1\).
At fifth query the answer is \(\max(1,0,1) = 1\).