卡片查询问题

题目描述

我们有 $N$ 个编号为 $1$ 到 $N$ 的盒子,初始时均为空,另有无限张空白卡片。

按顺序处理 $Q$ 个查询,查询共有以下三种类型。

1 i j : 在一张空白卡片上写上数字 $i$,放入盒子 $j$。

2 i : 将盒子 $i$ 中所有卡片上写有的数字按升序输出。

3 i : 将所有含有写有数字 $i$ 的卡片的盒子编号按升序输出。

这里,请注意以下几点。

在第二类查询中,如果盒子 $i$ 中有多张写有相同数字的卡片,该数字要按卡片张数重复输出。

在第三类查询中,即使某个盒子中有多张写有数字 $i$ 的卡片,该盒子的编号也只输出一次。

输入格式

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

$N$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

其中,$\mathrm{query}_q$ 表示第 $q$ 个查询,格式为以下三种之一:

$1$ $i$ $j$

$2$ $i$

$3$ $i$

输出格式

按顺序回答第二类和第三类查询。

对于每个此类查询,将需要输出的元素按升序排成一行,用空格分隔后输出。

样例

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

1 2
1 1 2
1 4
4

按顺序处理查询。

在卡片上写 $1$,放入盒子 $1$。

在卡片上写 $2$,放入盒子 $4$。

在卡片上写 $1$,放入盒子 $4$。

盒子 $4$ 中有写有数字 $1$ 和 $2$ 的卡片。

按此顺序输出 $1$ 和 $2$。

在卡片上写 $1$,放入盒子 $4$。

盒子 $4$ 中有写有数字 $1$、$1$ 和 $2$ 的卡片。

注意要把 $1$ 输出两次。

盒子 $1$ 和 $4$ 中有写有数字 $1$ 的卡片。

注意即使盒子 $4$ 中有两张写有数字 $1$ 的卡片,$4$ 也只输出一次。

盒子 $4$ 中有写有数字 $2$ 的卡片。

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

1 2 200000
1

数据范围

• $1 \le N, Q \le 2 \times 10^5$
• 第一类查询:
  • $1 \le i \le 2 \times 10^5$
  • $1 \le j \le N$
• 第二类查询:
  • $1 \le i \le N$
  • 给出该查询时,盒子 $i$ 中装有卡片。
• 第三类查询:
  • $1 \le i \le 2 \times 10^5$
  • 给出该查询时,存在装有写有数字 $i$ 的卡片的盒子。
• 需要输出的数字总数至多为 $2 \times 10^5$。
• 输入中的所有值均为整数。