Problem
ナタリア・コルシュノワはグリゴリー・メレホフが恋しくて、彼に戻りたいと思っています。しかし、残念なことに、グリゴリーはアクシーニャを愛しているので、ナタリアは自分が自分よりも優れていることを最愛の人に証明することにしました.
これを行うために、ナタリアはグリゴリーに行き、彼が提案したことは何でも、彼女はどんな問題でも解決できると宣言しました.メレホフは挑戦を受け入れました。
Grigory は、ナタリアに n 個の負でない整数で構成される A 配列を与えます。次に、次のような同じタイプの q 操作を実行するように彼女に依頼します。 k .さらに、l から r までの各インデックス i には、数値 k の代わりに数値 k が代入されます。 >A i であり、ビット単位の排他的 “or” と見なされます。セグメント \([l;r]\) 内のすべての数値。その後、数値 Ai 再び >i".
したがって、配列を変更しない \(r – l + 1\) 個の独立した置換があり、したがって \( r – l + 1\) は、ビット単位の排他的 “or ” になります。ナタリアは、グリゴリーにビット単位の排他的「または」を伝える必要があります。すべての置換結果 (理解を深めるために、例を確認してください)。
ナタリア・コルシュノワがこのタスクに対処するのを手伝ってください!そうすれば、グレゴリーは必ず彼女の元に戻ってきます!
入力
最初の行は整数 n (\(1 <= n <= 10^5\)) –配列要素の数。
2 行目には、\(10^8\) を超えない n 個の負でない整数が含まれています。
3 行目は整数 q (\(1 <= q <= 10^5\)) – です。リクエスト数。
以下には q 行が含まれ、それぞれに 3 つの整数が含まれています: l、r、k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
出力
クエリごとに
q の応答をスペースで区切って 1 行に出力する必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
説明
最初のリクエスト:
1) 7⊕ 2⊕ 3 = 6
2) 1⊕ 7⊕ 3 = 5
3) 1⊕ 2⊕ 7 = 4
6 ⊕ 5⊕ 4 = 7
答え: 7.
2 番目のリクエスト:
1) 10 ⊕ 5 = 15
2) 4⊕ 10 = 14
15 ⊕ 14 = 1
答え: 1.