問題文

$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$
• $2$ 番目の形式のクエリについて、
  • $1 \\leq i \\leq N$
  • このクエリが与えられる時点で箱 $i$ にカードが入っている
• $3$ 番目の形式のクエリについて、
  • $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$ 番目の形式のクエリに対し、順番に答えを出力せよ。
各クエリでは出力するべき要素を昇順に空白区切りで出力し、クエリごとに改行せよ。

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

入力例 2

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

出力例 2

1 2 200000
1