Harry Potter in CMS
本题没有可用的提交语言。
Description
Harry is participating in the Hogwarts Informatics Olympiad. There is $1$ problem with many subtasks. However, Voldemort has cast a spell on the judges, making them believe that Harry has copied in some of his submissions. To find out how Harry is doing in the competition considering Voldemort's spell, Harry will ask you $q$ queries.
The queries can be of $3$ types:
- $1$ $k$: Harry gives you information about a submission. He provides $k$ numbers $x_1, x_2, \ldots, x_k$, where each $x_i$ represents the index of a subtask that Harry has solved correctly in this submission. All the $x_i$ are distinct. Note that Harry may solve a subtask correctly that he had already solved correctly in a previous submission.
- $2$ $i$: Harry tells you that the judges have invalidated the submission he specified in query $i$. It is guaranteed that query $i$ is of type $1$ and that Harry had already made that query. It is also guaranteed that the submission had not been invalidated yet.
- $3$: You must print the number of submissions that are currently increasing Harry's score (considering only the previous queries). A submission increases Harry's score if, for any of the subtasks he solves correctly, it is the first submission that Harry has specified to you and has not been invalidated with that correct subtask yet.
The first line contains an integer $t$, the number of cases to answer. ($1 \le t \le 100$).
The first line of each case contains an integer $q$, the number of queries that Harry asks you. $(2 \le q \le 2 \cdot 10^5)$.
The following $q$ lines contain the queries. Line $j$ contains an integer $type_j$, indicating the type of the query ($1 \le type_j \le 3$). If $type_j = 1$, it will be followed by an integer $k_j$ and $k_j$ integers $x_{j_1}, x_{j_2}, \ldots, x_{j_k}$, the subtasks that Harry solves in that submission, ($1 \le x_{j_i} \le 2 \cdot 10^5$). If $type_j = 2$, it will be followed by an integer $i_j$, the index of the query specifying the invalidated submission.
It is guaranteed that both the sum of $q$ and the sum of $\sum k_j$ over all cases are at most $2 \cdot 10^5$.
For each case, you must print the number of submissions that are increasing Harry's score for each query of type $3$ that you receive.
Input
The first line contains an integer $t$, the number of cases to answer. ($1 \le t \le 100$).
The first line of each case contains an integer $q$, the number of queries that Harry asks you. $(2 \le q \le 2 \cdot 10^5)$.
The following $q$ lines contain the queries. Line $j$ contains an integer $type_j$, indicating the type of the query ($1 \le type_j \le 3$). If $type_j = 1$, it will be followed by an integer $k_j$ and $k_j$ integers $x_{j_1}, x_{j_2}, \ldots, x_{j_k}$, the subtasks that Harry solves in that submission, ($1 \le x_{j_i} \le 2 \cdot 10^5$). If $type_j = 2$, it will be followed by an integer $i_j$, the index of the query specifying the invalidated submission.
It is guaranteed that both the sum of $q$ and the sum of $\sum k_j$ over all cases are at most $2 \cdot 10^5$.
Output
For each case, you must print the number of submissions that are increasing Harry's score for each query of type $3$ that you receive.
2
10
1 3 3 2 5
3
1 1 3
1 1 2
2 1
3
2 3
3
2 4
3
11
1 2 2 3
1 1 2
1 1 3
1 1 5
3
2 1
3
1 2 2 3
2 2
2 3
3
1
2
1
0
2
3
2
Note
—
Problem idea: Esomer
Problem preparation: Esomer, Hectorungo18
Ocurrences: Novice 6