Есть последовательность \(a_0, a_1, a_2, \ldots\) бесконечной длины. Изначально \(a_i = i\) для каждого неотрицательного целого \(i\).
Каждый элемент последовательности будет одновременно изменяться через каждую секунду. \(a_i\) изменится на \(a_{i - 1} \mid a_i \mid a_{i + 1}\) для каждого положительного целого \(i\). \(a_0\) изменится на \(a_0 \mid a_1\). Здесь \(|\) обозначает побитовое ИЛИ.
Черепаха должна найти значение \(a_n\) после \(m\) секунд. В частности, если \(m = 0\), то он должен найти начальное значение \(a_n\). Он устал вычислять так много значений, поэтому пожалуйста, помогите ему!
Выходные данные
Для каждого теста выведите одно целое число — значение \(a_n\) после \(m\) секунд.
Примечание
Через \(1\) секунду, \([a_0, a_1, a_2, a_3, a_4, a_5]\) станет \([1, 3, 3, 7, 7, 7]\).
Через \(2\) секунды, \([a_0, a_1, a_2, a_3, a_4, a_5]\) станет \([3, 3, 7, 7, 7, 7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10
|
0
1
3
1
7
11
23
1279
19455
|