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 and 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 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).
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.
For each query of second type print the result on a single line.
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