/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。はじめ、A の要素は全て 0 です。
Q 個のクエリが与えられるので、順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。
1 x：A_x の値を 1 増やす。2：i=1,2,\ldots,N に対し、A_i \geq 1 ならば A_i の値を 1 減らす。
各クエリを処理した直後の A_1,A_2,\ldots,A_N のビット単位 \mathrm{XOR} を求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1\le N\le 5\times 10^5
- 1\le Q\le 5\times 10^5
- 1\le x\le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 x
2
出力
Q 行出力せよ。
i 行目 (1\le i\le Q) には、i 番目のクエリを処理した直後の A に対する A_1,A_2,\ldots,A_N のビット単位 \mathrm{XOR} を出力せよ。
入力例 1
2 5 1 2 1 2 1 1 2 2
出力例 1
1 2 3 1 0
1 番目のクエリを処理した後 A=(0,1) となります。0,1 のビット単位 \mathrm{XOR} は 1 なので、1 行目には 1 を出力してください。
2 番目のクエリを処理した後 A=(0,2) となります。0,2 のビット単位 \mathrm{XOR} は 2 なので、2 行目には 2 を出力してください。
3 番目のクエリを処理した後 A=(1,2) となります。1,2 のビット単位 \mathrm{XOR} は 3 なので、3 行目には 3 を出力してください。
4 番目のクエリを処理した後 A=(0,1) となります。0,1 のビット単位 \mathrm{XOR} は 1 なので、4 行目には 1 を出力してください。
5 番目のクエリを処理した後 A=(0,0) となります。0,0 のビット単位 \mathrm{XOR} は 0 なので、5 行目には 0 を出力してください。
入力例 2
3 8 1 2 1 3 1 1 1 2 1 1 2 1 3 1 1
出力例 2
1 0 1 2 1 0 1 2
Score : 300 points
Problem Statement
There is a length-N integer sequence A=(A_1,A_2,\ldots,A_N). Initially, all elements of A are 0.
You will be given Q queries, which should be processed in order. There are two types of queries, each given in one of the following formats:
1 x: Increase the value of A_x by 1.2: For each i=1,2,\ldots,N, if A_i \geq 1, decrease the value of A_i by 1.
Find the bitwise \mathrm{XOR} of A_1,A_2,\ldots,A_N immediately after processing each query.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, denoted A \oplus B, is defined as follows:
- In the binary representation of A \oplus B, the digit in the 2^k (k \geq 0) place is 1 if exactly one of the digits in the 2^k place of A and B in their binary representations is 1, and 0 otherwise.
More generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1\le N\le 5\times 10^5
- 1\le Q\le 5\times 10^5
- 1\le x\le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Each query is given in one of the following 2 formats:
1 x
2
Output
Output Q lines.
The i-th line (1\le i\le Q) should contain the bitwise \mathrm{XOR} of A_1,A_2,\ldots,A_N for A immediately after processing the i-th query.
Sample Input 1
2 5 1 2 1 2 1 1 2 2
Sample Output 1
1 2 3 1 0
After processing the first query, A=(0,1). The bitwise \mathrm{XOR} of 0,1 is 1, so output 1 on the first line.
After processing the second query, A=(0,2). The bitwise \mathrm{XOR} of 0,2 is 2, so output 2 on the second line.
After processing the third query, A=(1,2). The bitwise \mathrm{XOR} of 1,2 is 3, so output 3 on the third line.
After processing the fourth query, A=(0,1). The bitwise \mathrm{XOR} of 0,1 is 1, so output 1 on the fourth line.
After processing the fifth query, A=(0,0). The bitwise \mathrm{XOR} of 0,0 is 0, so output 0 on the fifth line.
Sample Input 2
3 8 1 2 1 3 1 1 1 2 1 1 2 1 3 1 1
Sample Output 2
1 0 1 2 1 0 1 2