Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Copy and Replace

By robin_aust · 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

    Discussion

    Statistics


    82% Solution Ratio

    YouKnowWhoEarliest, 6M ago

    YouKnowWhoFastest, 0.2s

    Superm4nLightest, 13 MB

    Deshi_TouristShortest, 2848B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.