HappyParadise

問題

$N$個部屋と$M$羽の鳩がいます。部屋と鳩はそれぞれ$1$から$N$、$1$から$M$と番号がついています。初期状態では鳩はどの部屋にも入っていません。

$Q$個のクエリが与えられるので順番に処理し、クエリをすべて処理した時点で各鳩がどの部屋に入っているか答えてください。クエリは3個の整数の組$(t,a,b)$で表されて、$t$の値によってクエリの種類が異なります。

• $t=1$のとき：部屋$a$に鳩$b$を入れます。このとき、部屋$a$は空であることおよび鳩$b$はどの部屋にも入っていないことが保証されます。
• $t=2$のとき：部屋$a$に入っている鳩を部屋から出します。$b$は常に$-1$が与えられます。このとき、部屋$a$は空でないことが保証されます。
• $t=3$のとき：鳩$b$を現在の部屋から出します。$a$は常に$-1$が与えられます。このとき、鳩$b$はいずれかの部屋に入っていることが保証されます。

制約

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 3・10^5$
• $1 \leq Q \leq 3・10^5$
• $1 \leq t \leq 3$
• $t=1$ ならば $1 \leq a \leq N, 1 \leq b \leq M$
• $t=2$ ならば $1 \leq a \leq N, b = -1$
• $t=3$ ならば $a = -1, 1 \leq b \leq M$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。ここで$query_i$は$i$番目のクエリを意味する。

$N \space\space M \space\space Q$
$query_1$
$query_2$
︙
$query_Q$

各クエリは次の形式で与えられる。

$t \space\space a \space\space b$

出力

クエリの処理をすべて終えた時点で、各鳩がどの部屋に入っているかをスペース区切りで出力せよ。 ただしどの部屋にも入っていない鳩は-1と出力すること。

サンプル

10 3 4
1 2 1
1 5 2
2 2 -1
1 8 1

8 5 -1

$1$番目のクエリでは鳩$1$が部屋$2$に入ります。 $2$番目のクエリでは鳩$2$が部屋$5$に入ります。 $3$番目のクエリでは部屋$2$から鳩$1$が出ます。 $4$番目のクエリでは鳩$1$が部屋$8$に入ります。 最終的に鳩$1$は部屋$8$に、鳩$2$は部屋$5$に、鳩$3$はどの部屋にも入っていないので答えは出力例の通りとなります。

1 1 2 
1 1 1
3 -1 1

-1

全てのクエリを処理した後にどの部屋にも鳩が入っていない場合もあります。