Array and queries

5

6 votes
Medium, Ad-Hoc, Lazy Propagation in Interval/Segment Trees, Advanced Data Structures, Data Structures, 普通
Problem

Given an array a of size 2n indexed from 0 to 2n1 and q queries of type:

  • 1lr (0lr<2n): Print max(al,al+1,,ar).

  • 2lrv (0lr<2n,0v109): Assign value v to every ai (lir).

  • 3k (0k<2n): Permute array a by permutation p, pi=iXORk. Because 0k<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 (0n18) and q (1q218).

The second line contains 2n numbers - a0,a1,,a2n1 (0ai109) 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.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?