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.