球与袋子查询

题目描述

你有一个空袋子。 给定 $Q$ 个查询，需要按顺序处理。

共有三种类型的查询：

• 1 x：往袋子里放入一个写着整数 $x$ 的球。
• 2 x：从袋子里取出一个写着整数 $x$ 的球并丢弃。保证执行该查询时袋子里存在写着整数 $x$ 的球。
• 3：输出袋中球上写着的不同整数的个数。

输入格式

输入按以下格式从标准输入给出：

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

第 $i$ 个查询 $\text{query}_i$ 以以下三种格式之一给出：

$1$ $x$

$2$ $x$

$3$

输出格式

如果第三类查询共有 $K$ 个，则输出 $K$ 行。 第 $i$ 行（$1 \leq i \leq K$）输出第 $i$ 个第三类查询的答案。

样例

8
1 3
1 1
1 4
3
2 1
3
1 5
3

3
2
3

初始时袋子是空的。

对于第 1 个查询 1 3，一个写着整数 $3$ 的球进入袋子。

对于第 2 个查询 1 1，一个写着整数 $1$ 的球进入袋子。

对于第 3 个查询 1 4，一个写着整数 $4$ 的球进入袋子。

对于第 4 个查询 3，袋子里有写着整数 $1, 3, 4$ 的球，因此输出 $3$。

对于第 5 个查询 2 1，从袋子里取出一个写着整数 $1$ 的球。

对于第 6 个查询 3，袋子里有写着整数 $3, 4$ 的球，因此输出 $2$。

对于第 7 个查询 1 5，一个写着整数 $5$ 的球进入袋子。

对于第 8 个查询 3，袋子里有写着整数 $3, 4, 5$ 的球，因此输出 $3$。

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

1
1

数据范围

• $1 \leq Q \leq 2 \times 10^{5}$
• $1 \leq x \leq 10^{6}$
• 当给出第二类查询时，袋子里存在写着整数 $x$ 的球。
• 至少有一个第三类查询。
• 所有输入值均为整数。