分数: 300 点
问题陈述
我们有 N 盒子编号 1 to N 最初是空的,并且空白卡的数量不受限制。
流程 Q 按顺序查询。查询有以下三种。
1 i j\colon 写入号码 i 在一张空白卡上并将其放入盒子中 j.2 i\colon 报告框中卡片上写的所有数字 i, 按升序排列.3 i\colon 报告包含该号码的卡片的箱子的所有箱子号码 i, 按升序排列.
此处,请注意以下事项。
- 在第二类查询中,if 框 i 包含多张具有相同号码的卡片,该号码的打印次数应等于这些卡片的数量。
- 在第三类查询中,即使一个盒子包含多张卡片,其编号为 i,该箱子的箱号只能打印一次。
约束
- 1 \leq N, Q \leq 2 \times 10^5
- 对于第一类查询:
- 1 \leq i \leq 2 \times 10^5
- 1 \leq j \leq N
- 对于第二类查询:
- 1 \leq i \leq N
- 盒子 给出此查询时, i 包含一些卡片。
- 对于第三类查询:
- 1 \leq i \leq 2 \times 10^5
- 有些盒子里有一张卡片,上面有号码 i 给出此查询时。
- 最多 将报告 2 \times 10^5 号码。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_q 表示 q-th 查询,采用以下格式之一:
1 i j
2 i
3 i
输出
按顺序回答第二类和第三类询问。
对于每个查询,打印一行包含要报告的元素 按升序排列,中间有空格。
示例输入 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
让我们按顺序处理查询。
- 写 1 放在卡片上并将其放入盒子中 1.
- 写 2 放在卡片上并将其放入盒子中 4.
- 写 1 放在卡片上并将其放入盒子中 4.
- 盒子
给出此查询时, 4 包含带有数字的卡片 1 和 2.
- 打印 1 和 2 按此顺序。
- 写 1 放在卡片上并将其放入盒子中 4.
- 盒子
给出此查询时, 4 包含带有数字的卡片 1, 1,和 2.
- 请注意,您应该打印 1 两次。
- 盒子 1 和 4 包含一张带有编号的卡片 1.
- 请注意,您应该打印 4 仅一次,即使盒子 4 包含两张卡片,其编号为 1.
- 盒子 4 包含一张卡片,其编号为 2.
示例输入 2
1 5 1 1 1 1 2 1 1 200000 1 2 1 3 200000
示例输出 2
1 2 200000 1