1981B.md (1477B)
1 Source: https://codeforces.com/problemset/problem/1981/B 2 3 B. Turtle and an Infinite Sequence 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a sequence $a_0, a_1, a_2, \ldots$ of infinite length. Initially $a_i = i$ for every non-negative integer $i$. 22 23 After every second, each element of the sequence will simultaneously change. $a_i$ will change to $a_{i - 1} \mid a_i \mid a_{i + 1}$ for every positive integer $i$. $a_0$ will change to $a_0 \mid a_1$. Here, $|$ denotes [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 24 25 Turtle is asked to find the value of $a_n$ after $m$ seconds. In particular, if $m = 0$, then he needs to find the initial value of $a_n$. He is tired of calculating so many values, so please help him! 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains two integers $n, m$ ($0 \le n, m \le 10^9$). 32 33 Output 34 35 For each test case, output a single integer — the value of $a_n$ after $m$ seconds. 36 37 Example 38 39 Input 40 41 ``` 42 9 43 44 0 0 45 46 0 1 47 48 0 2 49 50 1 0 51 52 5 2 53 54 10 1 55 56 20 3 57 58 1145 14 59 60 19198 10 61 ``` 62 63 Output 64 65 ``` 66 0 67 1 68 3 69 1 70 7 71 11 72 23 73 1279 74 19455 75 ``` 76 77 Note 78 79 After $1$ second, $[a_0, a_1, a_2, a_3, a_4, a_5]$ will become $[1, 3, 3, 7, 7, 7]$. 80 81 After $2$ seconds, $[a_0, a_1, a_2, a_3, a_4, a_5]$ will become $[3, 3, 7, 7, 7, 7]$.