Bobo has two sequences and . He would like to perform the following operations:

+ , change the value of to y.
+ , change the value of to y.
+ , find the value of , where , .

输入描述:

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers n and m , which are the length of the two sequences and the number of operations. The second line contains n integers . The third line contains n integers . Each of the last m lines contains a query.

* 
* 
* 
* The sum of n and the sum of m do not exceed .

输出描述:

For each query of , output an integer denoting the value of .

4 9
1 2 3 3
-1 2 3 3
3 1
3 2
3 3
3 4
2 2 -4
3 1
3 2
3 3
3 4

1
3
6
9
1
2
5
8