Given an array a of size 2n indexed from 0 to 2n−1 and q queries of type:
1lr (0≤l≤r<2n): Print max(al,al+1,…,ar).
2lrv (0≤l≤r<2n,0≤v≤109): Assign value v to every ai (l≤i≤r).
3k (0≤k<2n): Permute array a by permutation p, pi=iXORk. Because 0≤k<2n 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 vpi=si.
Input
The first line contains numbers n (0≤n≤18) and q (1≤q≤218).
The second line contains 2n numbers - a0,a1,…,a2n−1 (0≤ai≤109) separated by space.
Each of the next q lines contains one type of query from the above mentioned types of queries.
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.