問題

NN人の人がいます。各人には背番号が割り当てられており、ii番目の人の背番号はAiA_iです。

初め、各人はそれぞれ異なるグループに所属しており、一人だけのグループとなっています。QQ個のクエリが与えられるので、それに従って以下の操作を順に行ってください。

  • Ti=1T_i = 1の時、人xxがいるグループと人yyがいるグループを1つにする。すでに同じグループになっている場合はなにもしない。
  • Ti=2T_i = 2の時、xx番目の人が所属するグループの全ての人の背番号のxorした結果を求める。

制約

  • 1N1051 \leqq N \leqq 10^{5}
  • 1Q1051 \leqq Q \leqq 10^{5}
  • 1Ai1091 \leqq A_i \leqq 10^{9}
  • TiT_i11もしくは22
  • 1x,yN1 \leqq x, y \leqq N
  • 入力はすべて整数。

入力

N
A_1 A_2 ... A_N
Q
Query_1
...
Query_Q

クエリは以下の形式で与えられる Ti=1T_i = 1の時、

1 x y

Ti=2T_i = 2の時、

2 x

入力例1

4
1 2 3 4
3
2 1
1 2 3
2 2

出力例1

1
1

はじめに各チームにいるのは(A1),(A2),(A3),(A4)(A_1), (A_2), (A_3), (A_4)となっています。

1つめのクエリでA1A_1がいるチームはA1A_1しかいないのでxorは11となります。

2つめのクエリで各チームは(A1),(A2, A3),(A4)(A_1), (A_2, A_3), (A_4)となります。

3つめのクエリでA2A_2がいるチームのxorは2\xor3=12 \xor 3 = 1となります。

入力例2

10
84 30 2 52 33 74 234 45 99 145
5
1 3 2
2 3
1 3 1
2 9
2 3

出力例2

28
99
72

Submit


Go (1.21)