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 A and B both of N integers, your will process Q queries of the following 3 types:
Find the maximum value in the range [L,R] in array A
Update A[I] with X
Replace the subarray A[L1…R1] with subarray B[L2…R2]. That means set A[L1]=B[L2],A[L1+1]=B[L2+1],A[L1+2]=B[L2+2],...,A[R1]=B[R2].
Input
The first line contains two integers N(1≤N≤106) and Q(1≤Q≤106), the number of elements in the arrays and the number of queries respectively.
The second line contains N integers A1,A2,…,AN(1≤Ai≤109), the elements of the array A.
The third line contains N integers B1,B2,…,BN(1≤Bi≤109), the elements of the array B.
The next Q lines describe the queries. Each line contains a query in the following form:
1 L R − find the maximum value in the range [L,R] (1≤L≤R≤N) in array A
2 I X − update A[I],(1≤I≤N) with X(1≤X≤109)
3 L1 R1 L2 R2 − replace the subarray A[L1…R1] with subarray B[L2…R2], where (1≤L1≤R1≤N),(1≤L2≤R2≤N) and (R1−L1+1=R2−L2+1)
Output
Print the output of each query of type 1.
Sample
Input | Output |
---|
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
|