eolymp
bolt
Try our new interface for solving problems
Problems

Знову запити?...

Знову запити?...

Time limit 3.5 seconds
Memory limit 256 MiB

Всі учасники дуже втомилися від задач на запити, кожен контест повинен мати хоча б одну таку задачу. Ось і вона...

Вам дано масив цілих чисел A довжини n. Вам треба обробляти наступні запити:

  • l r x — присвоїти кожному елементу на відрізку [l;r] значення a_i := a_i\&x, де \& — знак побітового I (AND).

  • ? — вивести максимальне значення \gcd(a_i,a_j) по всім парам 1 \le i < j \le n та \min(a_i,a_j) > 0. Якщо такої пари нема — виведіть 0.

У вхідних даних будуть лише запити першого типу. Вважайте, що після кожного запиту першого типу йде запит другого типу. Також до першого запита першого типу треба вивести відповідь на запит другого типу.

Через \gcd(a,b) тут позначено найбільший спільний дільник чисел a і b. Наприклад, \gcd(12,16) = 4, а \gcd(15,31) = 1.

Input data

Перший рядок містить два цілі числа n (1 \le n \le 2 \cdot 10^5) та q (1 \le q \le 2 \cdot 10^5) — кількість елементів масиву та кількість запитів першого типу.

Наступний рядок містить n цілих чисел a_i (0 \le a_i < 2^{20}) — елементи масиву.

Далі йдуть q рядків, кожен з яких містить три цілі числа l, r(1 \le l \le r \le n) та x(0 \le x < 2^{20}) — опис запита.

Output data

Виведіть q+1 рядок — відповіді на запити другого типу.

Examples

Input example #1
3 2
15 16 6
1 3 30
1 2 4
Output example #1
3
2
2
Input example #2
10 7
27 23 6 20 4 7 27 4 21 13
9 10 17
2 9 24
8 8 26
5 5 10
2 5 6
7 10 16
9 9 6
Output example #2
27
27
16
16
16
8
16
1

Note

Пояснення до першого прикладу:

До виконання операцій першого типу маємо масив [15,16,6], максимальне \gcd дорівнює \gcd(15,6) = 3.

Після першої операції маємо масив [14,16,6], максимальне \gcd дорівнює \gcd(14,16) = \gcd(14,6) = \gcd(16,6) = 2.

Після другої операції маємо масив [4,0,6], максимальне \gcd дорівнює \gcd(4,6) = 2.

Scoring

Рішення, які правильно працюють для n,q \le 1000, набиратимуть принаймні 25 балів.

Рішення, які правильно працюють для n,q \le 10000, набиратимуть принаймні 45 балів.

Author Andrii Stolitnii
Source ВЮДОІ 2023. I відбірковий тур