Subarray Replacement

Limits 4s, 256 MB

You are one of the greatest programmers of the decade. Ahasan heard that you can solve range query problems in a minute. He came to you with the following problem.

Given two arrays AA and BB both of NN integers, your will process QQ queries of the following 33 types:

  1. Find the maximum value in the range [L,R][L,R] in array AA

  2. Update A[I]A[I] with XX

  3. Replace the subarray A[L1R1]A[L_1… R_1] with subarray B[L2R2]B[L_2… R_2]. That means set A[L1]=B[L2],A[L1+1]=B[L2+1],A[L1+2]=B[L2+2],...,A[R1]=B[R2]A[L_1]=B[L_2], A[L_1+1]=B[L_2+1], A[L_1+2]=B[L_2+2],..., A[R_1]=B[R_2].

Input

The first line contains two integers N(1N106)N (1\leq N\leq 10^6) and Q(1Q106)Q (1\leq Q\leq 10^6), the number of elements in the arrays and the number of queries respectively.

The second line contains NN integers A1,A2,,AN(1Ai109)A_1, A_2, …,A_N (1\leq A_i\leq 10^9), the elements of the array AA.

The third line contains NN integers B1,B2,,BN(1Bi109)B_1, B_2, …, B_N (1\leq B_i\leq 10^9), the elements of the array BB.

The next QQ lines describe the queries. Each line contains a query in the following form:

Output

Print the output of each query of type 11.

Sample

InputOutput
6 5
3 7 9 2 4 1
9 2 5 6 1 5
1 2 5
3 1 4 3 6
1 2 5
2 2 4
1 1 6
9
6
5