AT_abc470_c [ABC470C] Inc, Dec, Xor

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. For example, $ 3 \oplus 5 = 6 $ (in binary: $ 011 \oplus 101 = 110 $ ). 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 $ .

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 $ 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 Explanation 1 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. ### 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.