F. Fence Painting
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Legendary Huron has a fence with $$$n$$$ planks, numbered from $$$0$$$ to $$$n-1$$$. Each plank has a brightness value, where the $$$i$$$-th plank initially has brightness $$$a_i$$$.

He also has a painting machine that can be used to paint a contiguous sequence of planks. This painting machine has $$$n$$$ paint slots numbered from $$$0$$$ to $$$n-1$$$, where the paint in the $$$i$$$-th slot has brightness $$$b_i$$$. To use this machine, Legendary Huron first selects a range of planks $$$[l,r]$$$ to paint them and an initial paint slot $$$k$$$, then the painting machine recolors the $$$l$$$-th plank using its $$$k-th$$$ paint slot, recolors the $$$(l+1)$$$-th plank using its $$$((k+1) \% n)$$$-th paint slot, ..., recolors the $$$r$$$-th plank using its $$$((k+r-l) \% n)$$$-th paint slot. In other words, it changes the brightness of the $$$i$$$-th plank to $$$b_{(k+i-l)\%n}$$$ for all $$$i \in [l,r]$$$.

Legendary Huron is a fan of beautiful fences. He defines the beauty of a sequence of $$$m$$$ planks with brightness $$$c_0, c_1, \dots, c_{m-1}$$$ as follows:

$$$$$$ \max_{0 \leq i \leq j \lt m}(c_j-c_i) $$$$$$

During the following $$$q$$$ days, Legendary Huron will perform one of two possible actions: repainting a sequence of planks using his painting machine or taking a photo of a sequence of planks. The action of Legendary Huron in the $$$i$$$-th day can be represented in the following way:

  1. Given three integers $$$l$$$, $$$r$$$, $$$k$$$, he will repaint the planks in the range $$$[l,r]$$$ and the initial paint slot for the painting machine will be the $$$k$$$-th slot. After repainting the planks, he wants to know the beauty of the whole fence.
  2. Given two integers $$$l$$$ and $$$r$$$, he will take a photo of the planks in the range $$$[l,r]$$$. After taking the photo, he wants to know the beauty of the sequence of planks that appears in the photo.

Help Legendary Huron to find the required beauty after each action.

Input

The first line contain two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$).

The second line contain $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$|a_i| \leq 10^9$$$).

The third line contain $$$n$$$ integers $$$b_0, b_1, \dots, b_{n-1}$$$ ($$$|b_i| \leq 10^9$$$).

The following $$$q$$$ lines starts with an integer $$$t$$$ ($$$t \in \{1,2\}$$$). If $$$t=1$$$, then three integers $$$l$$$, $$$r$$$, $$$k$$$ follows ($$$0 \leq l \leq r \leq n - 1$$$ and $$$0 \leq k \leq n - 1$$$), denoting that Legendary Huron will repaint planks as described above. If $$$t=2$$$, then two integers $$$l$$$ and $$$r$$$ follows ($$$0 \leq l \leq r \leq n - 1$$$), denoting that Legendary Huron will take a photo as described above.

Output

After each action, print one line with the required beauty.

Examples
Input
4 5
1 3 2 5
2 6 4 9
2 0 1
2 2 3
1 0 3 2
2 0 1
2 2 3
Output
2
3
5
5
4
Input
4 2
-1 2 4 6
1 1 1 1
2 0 3
1 0 0 3
Output
7
5