Problem Description

A programming contest is being held. There are $ N $ participants in this contest, and $ M $ problems are posed. The participants are numbered $1, 2, \ldots, N$, and the problems are numbered $1, 2, \ldots, M$.

In this contest, the score of a problem changes depending on the number of people who have solved it. Specifically, the score is $N - \text{(the number of people who have solved this problem so far)}$.

A participant's score is the sum of the scores of the problems they have solved. Note that if the score of a problem changes, the participant's score also changes. For example, in the case of $ N=2, M=1 $, the initial score of problem $ 1 $ is $ 2 $. When participant $ 1 $ solves problem $ 1 $, the score of problem $ 1 $ becomes $ 1 $, and participant $ 1 $'s score becomes $ 1 $. Further, when participant $ 2 $ solves problem $ 1 $, the score of problem $ 1 $ becomes $ 0 $, and both participants $ 1 $ and $ 2 $ have a score of $ 0 $.

Process $ Q $ queries $s_1, s_2, \ldots, s_Q$ given in the following format in order:

• Output the current score of participant $ n $. Given in the format 1 n.
• Participant $ n $ has solved problem $ m $. Given in the format 2 n m.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ s_1 $ $\vdots$ $ s_Q $

Output Format

For queries given in the format 1 n, output the current score of participant $ n $ in the given order.

Sample Input and Output

Sample Input #1

2 1 6
2 1 1
1 1
1 2
2 2 1
1 1
1 2

Sample Output #1

1
0
0
0

Sample Input #2

5 5 30
1 3
2 3 5
1 3
2 2 1
2 4 5
2 5 2
2 2 3
1 4
2 4 1
2 2 2
1 1
1 5
2 5 3
2 4 4
1 4
1 2
2 3 3
2 4 3
1 3
1 5
1 3
2 1 3
1 1
2 2 4
1 1
1 4
1 5
1 4
1 1
1 5

Sample Output #2

0
4
3
0
3
10
9
4
4
4
0
0
9
3
9
0
3

Notes/Hints

Constraints

• $1 \leq N, Q \leq 10^5$
• $1 \leq M \leq 50$
• $ s_i $ is one of the following formats:
• 1 n $(1 \leq n \leq N)$
• 2 n m $(1 \leq n \leq N, 1 \leq m \leq M)$
  • No participant solves the same problem multiple times.

Sample Explanation 1

• Initially, the score of problem $ 1 $ is $ 2 $, and both participants $ 1 $ and $ 2 $ have a score of $ 0 $.
• In the first query, participant $ 1 $ solves problem $ 1 $, making the score of problem $ 1 $ $ 1 $ and participant $ 1 $'s score $ 1 $.
• In the second query, participant $ 1 $'s score of $ 1 $ is output.
• In the third query, participant $ 2 $'s score of $ 0 $ is output.
• In the fourth query, participant $ 2 $ solves problem $ 1 $, making the score of problem $ 1 $ $ 0 $ and both participants $ 1 $ and $ 2 $ have a score of $ 0 $.
• In the fifth query, participant $ 1 $'s score of $ 0 $ is output.
• In the sixth query, participant $ 2 $'s score of $ 0 $ is output.

见题面 Input 部分

见题面 Output 部分