Pair Sum Queries

Given integer arrays a and b, process two types of queries in order: 0 i x increases a[i] by x, where i is a 0-based index; 1 x asks for the number of index pairs (i,j) such that a[i]+b[j]=x. Different positions are counted separately.

输入格式

The first line contains n m q. The second line contains the n integers of a, the third line contains the m integers of b, and the next q lines are queries. Site-supplemented ranges: 1≤n,m≤200000, 1≤q≤200000; initial values, increments, and targets have absolute value ≤10^9, and every updated a[i] is guaranteed to have absolute value ≤10^12; it is also guaranteed that over all type 1 queries, Σ min(Da,Db)≤10^7, where Da and Db are the numbers of distinct values in a and b at the time of that query. This limit corresponds to the program iterating over the smaller frequency table on each query.

输出格式

For each 1 x query, output the corresponding number of index pairs in order, separated by spaces; if there are no such queries, output an empty line.

样例 1

输入：

3 2 3
1 1 2
2 3
1 4
0 0 2
1 4

输出：

3 2

样例 2

输入：

1 1 1
0
0
1 0

输出：

1

样例 3

输入：

2 2 3
-1 4
2 -2
1 1
0 1 -3
1 1

输出：

1 1