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

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

Вам дано масив цілих чисел $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

Перший рядок містить два цілі числа $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

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

Examples

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$ балів.