B - ダイナミック・スコアリング 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 8 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

プログラミングコンテストが開催されます。 このコンテストの参加者は N 人で、コンテストには M 個の問題が出題されます。 参加者には 1,2,\ldots,N の番号が、問題には 1,2,\ldots,M の番号が振られています。

このコンテストにおいて、問題の得点はその問題を解いた人間の人数によって変化します。 具体的には、N - \text{(現時点でこの問題を解いた人数)} が得点となります。

参加者のスコアは解いた問題の得点の合計です。問題の得点が変化した場合、参加者のスコアも変化することに注意してください。 例えば、N=2, M=1 の場合において、はじめ問題 1 の得点は 2 です。 その後、参加者 1 が問題 1 を解いたとき、問題 1 の得点は 1、参加者 1 のスコアは 1 となります。 さらにその後、参加者 2 が問題 1 を解いたとき、問題 1 の得点は 0 となり、参加者 1,2 のスコアは 0 となることに注意してください。

以下の形式で与えられる Q 個のクエリ s_1, s_2, \ldots, s_Q を順番に処理してください。

  • 参加者 n の現在のスコアを出力せよ。 1 n という形式で与えられる。
  • 参加者 n が問題 m を解いた。2 n m という形式で与えられる。

制約

  • 1 \leq N, Q \leq 10^5
  • 1 \leq M \leq 50
  • s_i は下記のいずれかの形式の文字列
    • 1 n (1 \leq n \leq N)
    • 2 n m (1 \leq n \leq N, 1 \leq m \leq M)
      • どの参加者も同じ問題を複数回解くことはない

入力

入力は以下の形式で標準入力から与えられる。

N M Q
s_1
\vdots
s_Q

出力

1 n という形式で与えられたクエリに対して、与えられた順に参加者 n のその時点でのスコアを出力せよ。

入力例 1

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

出力例 1

1
0
0
0
  • はじめ、問題 1 の得点は 2、参加者 1,2 のスコアはどちらも 0 です。
  • 1 番目のクエリにおいて参加者 1 が問題 1 を解いたことにより、問題 1 の得点は 1、参加者 1,2 のスコアはそれぞれ 1,0 となります。
  • 2 番目のクエリにおいて参加者 1 のスコアである 1 が出力されます。
  • 3 番目のクエリにおいて参加者 2 のスコアである 0 が出力されます。
  • 4 番目のクエリにおいて参加者 2 が問題 1 を解いたことにより、問題 1 の得点は 0、参加者 1,2 のスコアはどちらも 0 となります。
  • 5 番目のクエリにおいて参加者 1 のスコアである 0 が出力されます。
  • 6 番目のクエリにおいて参加者 2 のスコアである 0 が出力されます。

入力例 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

出力例 2

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

Score : 8 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Contest

We will hold a programming contest. There will be N participants and M problems in this contest. The participants are numbered 1,2,\ldots,N, and the problems are numbered 1,2,\ldots,M.

In this contest, the score for a problem will depend on the number of participants who solve that problem. More specifically, the score is N - \text{(the number of participants who have solved the problem at the moment)}.

The score of a participant is the sum of the scores for the problems solved by that participant. Note that a change in the score for a problem will also change the score of participants. For example, in the case N=2 and M=1, the score for Problem 1 is initially 2. If Participant 1 solves Problem 1, the score for Problem 1 becomes 1, and his score also becomes 1. If Participant 2 then solves Problem 1, the score for Problem 2 becomes 0, and the score of Participant 1 and 2 both become 0.

Process Q queries s_1, s_2, \ldots, s_Q in order, which will be given in the formats below:

  • Print the current score of Participant n. This query is given in the format 1 n.
  • It is reported that Participant n solves Problem m. This query is given in the format 2 n m.

Constraints

  • 1 \leq N, Q \leq 10^5
  • 1 \leq M \leq 50
  • s_i is a string in 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.

Input

Input is given from Standard Input in the following format:

N M Q
s_1
\vdots
s_Q

Output

For each query in the format 1 n, in the order given, print the score of Participant n at that time.

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
  • Initially, the score for Problem 1 is 2, and the score of Participant 1 and 2 are both 0.
  • After Participant 1 solves Problem 1 in the first query, the score for Problem 1 becomes 1, and the score of Participant 1 and 2 becomes 1 and 0, respectively.
  • In the second query, the score of Participant 1 - which is 1 - is printed.
  • In the third query, the score of Participant 2 - which is 0 - is printed.
  • After Participant 2 solves Problem 1 in the fourth query, the score for Problem 1 becomes 0, and the score of Participant 1 and 2 both become 0.
  • In the fifth query, the score of Participant 1 - which is 0 - is printed.
  • In the sixth query, the score of Participant 2 - which is 0 - is printed.

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