Copy and Sum

There are two sequences, A and B, of length $N$. Denote the $i$-th elements of A and B by $a_i$ and $b_i$, respectively. $i$ is an integer between $1$ and $N$. Perform the following operations on these sequences of numbers.

• copy($x$, $y$, $z$) : replace $a_x, a_{x+1}, ..., a_{x+z-1}$ with $b_y, b_{y+1}, ..., b_{y+z-1}$ respectively.
• sum(p, q) : output the value of $a_p + a_{p+1} + ... + a_q$.

Given a sequence of numbers A and B and some operations, write a program that outputs the result of the sum operation.

Input

The input is given in the following form.

$N$ $M$
$a_1$ $a_2$ ... $a_N$
$b_1$ $b_2$ ... $b_N$
$op_1$
$op_2$
:
$op_M$

In the first line, the length of the sequence $N$ ($1 \leq N \leq 200,000$) and the number of operations $M$ ($1 \leq M \leq 200,000$) are given. In the next line, the $i$-th element $a_i$ ($0 \leq a_i \leq 1,000,000,000$) of sequence A is given as integers. In the next line, the $i$-th element $b_i$ ($0 \leq b_i \leq 1,000,000,000$) of sequence B is given as integers. In the following $M$ lines, the information $op_i$ indicating the operation is given. Each $op_i$ is given in one of the following forms.

0 $x$ $y$ $z$

or

1 $p$ $q$

If the first character is 0, it indicates that the operation copy($x$, $y$, $z$) is to be performed. Note that $1 \leq x,y \leq N, 1 \leq z,$ max$(x,y)+z-1 \leq N$, where max($x$,$y$) is the larger of $x$ and $y$. If the first letter is 1, it indicates that the operation sum($p$, $q$) is to be performed. Note that $1 \leq p \leq q \leq N$. The operation sum is given to the input one or more times.

Output

For each sum operation given, output the result of the sum in a line.

Sample Input and Output

Sample Input 1

5 5
1 3 5 7 9
2 4 6 8 10
1 1 3
1 4 5
0 4 1 2
1 1 3
1 4 5

Sample Output 1

9
16
9
6

Sample Input 2

6 5
1 2 3 4 5 6
2 4 8 16 32 64
1 1 6
0 1 4 3
1 1 6
0 3 1 3
1 1 6

Sample Output 2

21
127
68

 

---