Для массива \(b\) из \(m\) целых неотрицательных чисел определим \(f(b)\) как максимальное значение \(\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)\) среди всех неотрицательных целых чисел \(x\), где \(|\) обозначает операцию побитового ИЛИ.
Вам даны целые числа \(n\) и \(q\). Вы начинаете с пустого массива \(a\). Выполните следующие \(q\) запросов:
- \(v\): добавить \(v\) в конец \(a\) и вывести \(f(a)\). Гарантируется, что \(0 \leq v < n\).
Запросы даны в измененном виде.
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел, разделенных пробелами. \(i\)-е число должно равняться результату выполнения \(i\)-го запроса.
Примечание
В первом наборе входных данных в конце \(a=[1,2]\). Для \(i=1\) ответ всегда \(0\), независимо от \(x\). Для \(i=2\) мы можем выбрать \(x=5\).
Во втором наборе входных данных итоговое значение \(a=[3,1,0,5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 2
1 2
7 4
3 1 5 2
|
0 2
0 2 3 5
|