You are given two arrays each of length N(1 <= N <= 100000) which are initially filled with zeros. You have to apply M (1 <= M <= 100000) queries of three kind: 

0 arr left right :  calculate and output sum of elements from left to right in array arr (arr = 0 -- first array, arr = 1 -- second     array); 
1 arr idx newValue : change value of element at index idx of array arr on newValue;
2 left right :  swap range of elements of two arrays from left to right ( for i = left to right do swap(a[i], b[i]) );

Input

The first line of input contains two integers - N, M. The folowing M lines contains information about queries.
On each query - one line:
First integer number cmd contains 0, 1 or 2 (type of query described above).
if cmd equals 0, then following 3 integers arr, left, right - 0 <= arr <= 1, 0 <= left <= right <= N - 1.
if cmd equals 1, then following 3 integers arr, idx, newValue - 0 <= arr <= 1, 0 <= idx <= N - 1, -10000 <= newValue <= 10000.
if cmd equals 2, then following 2 integers left, right - 0 <= left <= right <= N - 1.

Output

On each query with cmd equals 0 you should output corresponding value described above.

Example

Input:
5 10
1 0 0 1
1 1 4 2
0 0 0 4
0 1 0 4
2 0 0
0 0 0 4
0 1 0 4
2 0 4
0 0 0 4
0 1 0 4

Output:
1
2
0
3
3
0