Range XORクエリ
与えられた配列には
n 個の要素があり、合計で q 件のクエリが存在します。クエリの種類は2つあります:- 指定された範囲のXOR（排他的OR）値を求めるクエリ
- 指定した位置の配列要素を更新するクエリ
これらのクエリに対して、効率よく処理を行うことが求められます。
入力
最初の行には、配列の要素数
n とクエリの数 q (1 ≤ n, q ≤ 100 000) が空白区切りで与えられます。次の行には、
n 個の要素 () が空白区切りで与えられます。これは配列の初期状態を表しています。続く
q 行それぞれがクエリを示し、形式は以下の2種類です:- 範囲のXORを求めるクエリ: 行の先頭が
1で、続いて と () が与えられます。このとき、インデックス範囲[]内に含まれる要素のXOR値を出力してください。
- 配列を更新するクエリ: 行の先頭が
2で、続いて と () が与えられます。このとき、配列のインデックス にある要素を新しい値 に書き換えてください。
出力
範囲のXORクエリが与えられるたびに、その範囲内の要素のXOR値を一行ごとに出力してください。
例
入力 | 出力 |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 7
9
3 |
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 1 MB