题目描述

$1$ から $N$ までの番号がついた $N$ 個の空の箱と、何も書かれていない無数のカードがあります。
$Q$ 個のクエリが与えられるので、順番に処理してください。クエリは次の $3$ 種類のいずれかです。

• 1 i j $\colon$ カードを $1$ 枚選んで数 $i$ を書き込み、そのカードを箱 $j$ に入れる
• 2 i $\colon$ 箱 $i$ に入っているカードに書かれた数を昇順ですべて答える
• 3 i $\colon$ 数 $i$ が書かれたカードが入っている箱の番号を昇順ですべて答える

ただし、以下の点に注意してください。

• $2$ 番目の形式のクエリにおいては、箱 $i$ の中に同じ数が書かれたカードが複数枚あるときは、入っている枚数と同じ回数だけその数を出力する
• $3$ 番目の形式のクエリにおいては、数 $i$ が書かれたカードが同じ箱に複数枚入っている場合でも、その箱の番号は $1$ 度だけ出力する

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 番目の形式のクエリに対し、順番に答えを出力せよ。
各クエリでは出力するべき要素を昇順に空白区切りで出力し、クエリごとに改行せよ。

题目大意

给定 $n$ 个盒子，你需要满足一下三种操作：

$1\ i\ j$，把数字 $i$ 扔到盒子 $j$ 里面；

$2\ i$，查询盒子 $i$ 里面的数字，按升序输出；

$3\ i$，查询数字 $i$ 出现在的盒子编号，按升序输出。（若多个同一数字出现在一个盒子，那么这个盒子编号只输出一次。）

translated by 月。

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
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

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$ 個以下
• 入力はすべて整数

Sample Explanation 1

クエリを順に処理していきます。 - カードに $1$ を書き込み、箱 $1$ に入れます。 - カードに $2$ を書き込み、箱 $4$ に入れます。 - カードに $1$ を書き込み、箱 $4$ に入れます。 - 箱 $4$ に入っているカードに書かれた数は $1,\ 2$ です。 - $1,\ 2$ の順に出力してください。 - カードに $1$ を書き込み、箱 $4$ に入れます。 - 箱 $4$ に入っているカードに書かれた数は $1,\ 1,\ 2$ です。 - $1$ を $2$ 度出力することに注意してください。 - 数 $1$ が書かれたカードが入っている箱は箱 $1,\ 4$ です。 - 箱 $4$ には数 $1$ が書かれたカードが $2$ 枚入っていますが、$4$ は $1$ 回しか出力しないことに注意してください。 - 数 $2$ が書かれたカードが入っている箱は箱 $4$ です。