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 and both of integers, your will process queries of the following types:
Find the maximum value in the range in array
Replace the subarray with subarray . That means set .
The first line contains two integers and , the number of elements in the arrays and the number of queries respectively.
The second line contains integers , the elements of the array .
The third line contains integers , the elements of the array .
The next lines describe the queries. Each line contains a query in the following form:
find the maximum value in the range in array
replace the subarray with subarray , where and
Print the output of each query of type .
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