Count Ways to Reach a Sum

Array a never changes. Operation 0 i x increases b[i] by x; operation 1 target asks how many index pairs (i,j) satisfy a[i]+b[j]=target. Initially, the values within each array are distinct; after updates, duplicates are allowed, and pairs are counted by index.

This site's standard input/output is stated explicitly.

输入格式

The first line contains na nb q, followed by two lines with arrays a and b, then q lines of operations. This site uses 1≤na≤100 and 1≤nb,q≤100000; initial values and increments are −10⁹..10⁹, target is −10¹⁴..10¹⁴, and indices start from 0.

输出格式

For each query operation, output one line with the number of pairs; if there are no queries, output an empty line.

样例 1

输入：

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

输出：

2
2

样例 2

输入：

1 1 2
0
1
0 0 -1
1 0

输出：

1

样例 3

输入：

1 1 1
1
2
1 9

输出：

0

样例说明

Example 1: initially there are two pairs, 1+3 and 2+2; after the update b is 3, 3, and both distinct indices pair with 1, so the count is still 2. Example 2: the update makes b equal to 0, and the query for sum 0 has 1 pair. Example 3: no combination sums to 9, so the output is 0.