E - Exclusive OR Queries Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の整数列 A_1, A_2, \ldots, A_N があります。以下の Q 個のクエリを順番に処理してください。

  • 値が L_i 以上 R_i 以下である要素をすべて選び、それらの排他的論理和を答える。その後、選んだ要素をすべて X_i に更新する。 ただし、L_i 以上 R_i 以下の整数が 1 つも存在しない場合の答えは 0 とする。

排他的論理和とは

整数 c_1, c_2, ..., c_n の排他的論理和 X は、以下のように定義されます。

  • X を二進数表記したときの 2^k (k \ge 0) の位の値は、c_1, c_2, ..., c_n のうち、二進数表記したときの 2^k の位の値が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。

例えば、3 と 5 の排他的論理和は 6 です(二進数表記すると: 011 と 101 の排他的論理和は 110 です)。

制約

  • 1\le N\le 3\times 10^5
  • 1\le Q\le 2\times 10^5
  • 0\le A_i\le 10^9
  • 0\le L_i\le R_i\le 10^9
  • 0\le X_i\le 10^9
  • 入力はすべて整数

入力

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

N\ Q
A_1\ A_2\ \ldots\ A_N
L_1\ R_1\ X_1
L_2\ R_2\ X_2
\vdots
L_Q\ R_Q\ X_Q

出力

Q 行出力してください。 i (1\le i\le Q) 行目には i 番目のクエリに対する答えを出力してください。

入力例 1

5 2
7 4 1 5 9
7 10 2
2 8 5

出力例 1

14
1
  • 1 つめのクエリでは、7 以上 10 以下の整数は 7 と 9 の 2 つなのでこれらの排他的論理和の 14 を出力します。 その後この 2 つを 2 に更新して、数列は \{2,4,1,5,2\} になります。
  • 2 つめのクエリでは、2 以上 8 以下の整数は 2, 4, 5, 2 の 4 つなのでこれらの排他的論理和の1 を出力します。 その後この 4 つを 5 に更新して、数列は \{5,5,1,5,5\} になります。

入力例 2

1 1
5
1 3 2

出力例 2

0

条件をみたす A_i が存在しない場合の答えは 0 です。このときは更新も行われません。

入力例 3

15 10
76 87 42 60 30 58 52 82 42 13 81 8 97 5 87
4 11 92
56 60 68
90 100 24
30 35 15
12 17 53
24 32 31
0 6 85
74 82 55
69 72 30
50 61 49

出力例 3

13
6
97
30
2
24
0
79
0
3