Copy and Replace

robin_aust Intra AUST Programming Co...
Limits 1s, 512 MB

We have to do a lot of assignments during our university life, some of which are pretty boring. So, we often do copy and paste. Most of us have already mastered that particular skill. But you know some of our teachers are very strict and for that, we do copy and replace instead of copy and paste. I know you are already an expert at it and this problem is similar to copy and replace operation so solve it as fast as you can.

You are given two arrays of integers x1,x2,x3xn(0xi109;1in)x_{1}, x_{2}, x_{3}… x_{n} (0 ≤ x_{i} ≤ 10^9 ; 1 ≤ i ≤ n) and y1,y2,y3yn(0yi109;1in)y_{1}, y_{2}, y_{3}… y_{n} (0 ≤ y_{i} ≤ 10^9 ; 1 ≤ i ≤ n) of length n. Now you have to execute q queries of two types of the following form:

1 a b k : Copy the subsegment of array x of length k, starting from position a, into array y, starting from position b, that is, execute yb+j=xa+jy_{b + j} = x_{a + j} for all integer j (0 ≤ j < k). The given operation is correct — both subsegments do not touch nonexistent elements.

2 l r : Find and print the difference between maximum and minimum value from array y in range l to r(inclusive).

Input

The first line contains two integers n and q (1≤n≤100000, 1≤q≤100000) the length of the arrays and the number of queries correspondingly. The second line contains array x and the third line contains array y. Next q lines contain queries in the form described in the statement.

Output

For each query of second type print the result on a single line.

Sample

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

Submit

Login to submit.

Statistics

82% Solution Ratio
YouKnowWhoEarliest, Apr '21
YouKnowWhoFastest, 0.2s
Superm4nLightest, 13 MB
Deshi_TouristShortest, 2848B
Toph uses cookies. By continuing you agree to our Cookie Policy.