VRChat において、インスタンスとは、ユーザーが集まることができる空間の一つ一つのことです。

$N$ 人のプレイヤーと $M$ 個のインスタンスがあります。各インスタンスには待機列があります。インスタンスには $1,2,\ldots ,M$ と番号が付いています。

インスタンス $i$ の定員は $A _ i$ です。満員のインスタンスに対してプレイヤーが入場を試みたとき、そのプレイヤーは待機列の最後尾に並び、空きができるのを待つことになります。

はじめ、すべてのプレイヤーはどのインスタンスにも入場しておらず、またどの待機列にも並んでいません。$Q$ 個のクエリが与えられるので、順に処理してください。

• 1 x y : インスタンス移動

  プレイヤー $x$ が現在の居場所を一度離れた後、インスタンス $y$ への入場を試みる。正確には、以下の処理が順に発生する。

  • プレイヤー $x$ があるインスタンスに入場している場合、そのインスタンスからプレイヤー $x$ が退出する。そのインスタンスの待機列にプレイヤーがいる場合、待機列の先頭にいるプレイヤーがインスタンスに入場する。

  • プレイヤー $x$ があるインスタンスの待機列に並んでいる場合、プレイヤー $x$ は待機列から外れる。

  • インスタンス $y$ が満員である場合、プレイヤー $x$ がインスタンス $y$ の待機列の最後尾に並ぶ。

  • インスタンス $y$ が満員でない場合、プレイヤー $x$ がインスタンス $y$ に入場する。

• 2 z : 居場所判定

  • プレイヤー $z$ がインスタンスに入場している場合、そのインスタンスの番号を $p$ として 1 p を出力する。
  • プレイヤー $z$ が待機列に並んでいる場合、対応するインスタンスの番号を $p$ として 2 p を出力する。
  • 以上のどちらでもない場合、-1 を出力する。

なお、入出力が大きくなる場合があるので、高速な方法で入出力を行うことを推奨します。

• $1 \leq N \leq 500{,}000$
• $1 \leq M \leq 500{,}000$
• $1 \leq Q \leq 500{,}000$
• $1 \leq A_i \leq N$
• $1 \leq x \leq N$
• $1 \leq y \leq M$
• $1 \leq z \leq N$
• クエリ $2$ は $1$ つ以上存在する
• 入力はすべて整数

• $Q \leq 5{,}000$ を満たすデータセットに正解した場合は $50$ 点が与えられる。

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

$N$ $M$ $Q$
$A_1 \ A_2 \ \dots \ A_M$
$\mathrm{Query} _ 1$
$\mathrm{Query} _ 2$
$\vdots$
$\mathrm{Query} _ Q$

クエリ $2$ に対する回答を、与えられる順に $1$ 行に $1$ つずつ出力せよ。