問題文

web班ではKCS株式会社が管理している様々な業界のwebサイトに適切な広告をつける業務を行っています。新しく受注した広告をどの業界のwebサイトにつけるかを判別するプログラムを作ってください。

現在KCS会社の管理下にあるwebサイトについて以下の条件が与えられます。 webサイトは全部で $N$ 個あり、サイトの番号は $A_i(1 \leq i \leq N)$ で与えられます。 また、webサイト $B_i$ と $C_i$ は同じ業界に属しています。 なお、このような同じ業界に属しているサイトの組み合わせの情報も、webサイトの個数と同様に $N$ 個与えられます。

以下の状況において、広告が掲載される業界に含まれる最小のサイト番号を出力して下さい。

• 状況1・・・サイト $T$ が含まれる業界に広告を掲載する場合
• 状況2・・・丁度 $T$ 個のwebサイトを含む業界に広告を掲載する場合

$Q$ 個のクエリが与えられるので、それぞれのクエリで与えられる状況 $L(L=1||L=2)$ と条件に対して答えを出力して下さい。 条件に合う業界がない場合はNoneと出力して下さい。

• 回答は数字かNoneのどちらかで出力してください。

制約

• $3 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i,B_i,C_i \leq 10^9$
• $T_i$ は集合 $A$ に含まれる
• $N,Q,T,A_i,B_i,C_i$ は整数
• $L$ は1と2のどちらか

入力

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

ただし、 $\text{Query}_i$ は $i$ 番目のクエリを表します。 各クエリは以下の形式で与えられます。

出力

答えを出力して下さい。

サンプル

6
100 200 300 400 500 600
100 200
100 300
300 200
400 500
500 400
200 600
5
1 300
2 4
2 2
1 400
2 3

100
100
400
400
None