AT_aalc001_m NAND

For integers $ a,b $ that are at least $ 0 $ and less than $ 2^{30} $ , define the **NAND** of $ a $ and $ b $ as follows: - Represent each of $ a,b $ using $ 30 $ digits in base $ 2 $ , adding leading $ 0 $ s if necessary. For each digit, set the resulting digit to $ 0 $ if the corresponding digits of both numbers are $ 1 $ , and to $ 1 $ otherwise. This gives an integer represented by $ 30 $ digits in base $ 2 $ . This integer is the NAND of $ a $ and $ b $ . You are given a sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ consisting of integers that are at least $ 0 $ and less than $ 2^{30} $ . Process $ Q $ queries. Each query is of one of the following $ 2 $ types: - `1 p x`: Change $ A_p $ to the integer $ x $ , which is at least $ 0 $ and less than $ 2^{30} $ . - `2 l r`: Set $ B_l=A_l $ , and then, for $ i=l+1,l+2,\ldots,r $ in this order, define $ B_i $ as the NAND of $ B_{i-1} $ and $ A_i $ . Print $ B_r $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ p $ $ x $ > $ 2 $ $ l $ $ r $

Let $ q $ be the number of type $ 2 $ queries. Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th type $ 2 $ query.

### Sample Explanation 1 For query $ 1 $ , the answer can be calculated as follows: 1. $ B_1=A_1=5 $ . 2. The NAND of $ B_1 $ ( $ =5 $ ) and $ A_2 $ ( $ =3 $ ) is $ 1073741822 $ , so $ B_2=1073741822 $ . 3. The NAND of $ B_2 $ ( $ =1073741822 $ ) and $ A_3 $ ( $ =12 $ ) is $ 1073741811 $ , so $ B_3=1073741811 $ . 4. The NAND of $ B_3 $ ( $ =1073741811 $ ) and $ A_4 $ ( $ =10 $ ) is $ 1073741821 $ , so $ B_4=1073741821 $ . Print this value. ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \lt 2^{30} $ - For type $ 1 $ queries, $ 1 \leq p \leq N $ , $ 0 \leq x \lt 2^{30} $ - For type $ 2 $ queries, $ 1 \leq l \leq r \leq N $ - All numerical values in the input are integers.