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