配点 : $300$ 点

問題文

$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$ 度だけ出力する

制約

• $1 \leq N, Q \leq 2 \times 10^5$
• $1$ 番目の形式のクエリについて、- $1 \leq i \leq 2 \times 10^5$
  • $1 \leq j \leq N$
• $1 \leq i \leq 2 \times 10^5$
• $1 \leq j \leq N$
• $2$ 番目の形式のクエリについて、- $1 \leq i \leq N$
  • このクエリが与えられる時点で箱 $i$ にカードが入っている
• $1 \leq i \leq N$
• このクエリが与えられる時点で箱 $i$ にカードが入っている
• $3$ 番目の形式のクエリについて、- $1 \leq i \leq 2 \times 10^5$
  • このクエリが与えられる時点で数 $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$ 個目のクエリを表しており、次のいずれかの形式で与えられる。

$1$ $i$ $j$

$2$ $i$

$3$ $i$

出力

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

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, 2$ の順に出力してください。
• カードに $1$ を書き込み、箱 $4$ に入れます。
• 箱 $4$ に入っているカードに書かれた数は $1, 1, 2$ です。- $1$ を $2$ 度出力することに注意してください。
• $1$ を $2$ 度出力することに注意してください。
• 数 $1$ が書かれたカードが入っている箱は箱 $1, 4$ です。- 箱 $4$ には数 $1$ が書かれたカードが $2$ 枚入っていますが、$4$ は $1$ 回しか出力しないことに注意してください。
• 箱 $4$ には数 $1$ が書かれたカードが $2$ 枚入っていますが、$4$ は $1$ 回しか出力しないことに注意してください。
• 数 $2$ が書かれたカードが入っている箱は箱 $4$ です。

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

1 2 200000
1