Cards Query Problem

题目描述

有 $N$ 个编号从 $1$ 到 $N$ 的空箱子，以及无数张没有写字的卡片。
现在有 $Q$ 个操作，请按顺序处理。每个操作有以下三种类型之一：

• 1 i j ：选一张卡片，在上面写上数字 $i$，然后把这张卡片放进编号为 $j$ 的箱子里。
• 2 i ：请按升序输出编号为 $i$ 的箱子中所有卡片上写的数字。
• 3 i ：请按升序输出所有包含写有数字 $i$ 的卡片的箱子的编号。

请注意以下几点：

• 对于第 $2$ 种操作，如果箱子 $i$ 中有多张卡片上写着相同的数字，则该数字需要输出与卡片数量相同的次数。
• 对于第 $3$ 种操作，如果某个箱子中有多张卡片都写着数字 $i$，该箱子的编号只输出一次。

输入格式

输入按以下格式从标准输入读入。

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

其中，$\mathrm{query}_q$ 表示第 $q$ 个操作，格式如下之一：

$1$ $i$ $j$

$2$ $i$

$3$ $i$

输出格式

对于第 $2$ 种和第 $3$ 种操作，请按顺序输出答案。
每个操作输出的元素请按升序、用空格分隔，并且每个操作输出一行。

输入输出样例 #1

输入 #1

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

输出 #1

1 2
1 1 2
1 4
4

输入输出样例 #2

输入 #2

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

输出 #2

1 2 200000
1

说明/提示

限制条件

• $1 \leq N, Q \leq 2 \times 10^5$
• 对于第 $1$ 种操作：
  • $1 \leq i \leq 2 \times 10^5$
  • $1 \leq j \leq N$
• 对于第 $2$ 种操作：
  • $1 \leq i \leq N$
  • 保证操作时箱子 $i$ 中至少有一张卡片
• 对于第 $3$ 种操作：
  • $1 \leq i \leq 2 \times 10^5$
  • 保证操作时存在至少一个箱子中有写着数字 $i$ 的卡片
• 所有需要输出的数字总数不超过 $2 \times 10^5$
• 输入均为整数

样例解释 1

依次处理操作如下：

• 在卡片上写 $1$，放入箱子 $1$。
• 在卡片上写 $2$，放入箱子 $4$。
• 在卡片上写 $1$，放入箱子 $4$。
• 箱子 $4$ 中卡片上的数字为 $1, 2$。
• 请按 $1, 2$ 的顺序输出。
• 在卡片上写 $1$，放入箱子 $4$。
• 箱子 $4$ 中卡片上的数字为 $1, 1, 2$。
• 注意 $1$ 需要输出两次。
• 写有 $1$ 的卡片所在的箱子为 $1, 4$。
• 虽然箱子 $4$ 中有两张写有 $1$ 的卡片，但 $4$ 只输出一次。
• 写有 $2$ 的卡片所在的箱子为 $4$。