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.