Another query?...

All participants are very tired of query tasks, every contest should have at least one such task. Here it is...

You are given an array of $n$ integers $A$. You need to process the following queries:

• $lrx$ — assign each element on the segment $[l;r]$ the value $a_i:=a_i$ $\&$ $x$, where $\&$ is the bitwise AND operator.

• $?$ — output the maximum value of $\gcd (a_i,a_j)$ over all pairs $1\le i<j\le n$ such that $\min (a_i,a_j)>0$. If such a pair does not exist, output $0$.

The input will only contain queries of the first type. Assume that after each query of the first type there is a query of the second type. Also, before the first query of the first type, output the answer to the first query of the second type.

Here, $\gcd (a,b)$ denotes the greatest common divisor of $a$ and $b$. For example, $\gcd (12,16)=4$ and $\gcd (15,31)=1$.

Input

The first line contains two integers $n$ ($1\le n\le 2\cdot 10^5$) and $q$ ($1\le q\le 2\cdot 10^5$) — the number of elements in the array and the number of queries of the first type.

The next line contains $n$ integers $a_i$ ($0\le a_i<2^{20}$) — the array elements.

The next $q$ lines contain three integers each: $l$, $r$ $(1\le l\le r\le n)$ and $x$ $(0\le x<2^{20})$ — a description of the query.

Output

Output $q+1$ lines — the answers to the queries of the second type.

Examples

Note

Explanation for the first example:

Before performing any operations, we have the array $[15,16,6]$, and the maximum $\gcd$ is $\gcd (15,6)=3$.

After the first operation, we have the array $[14,16,6]$, and the maximum $\gcd$ is $\gcd (14,16)=\gcd (14,6)=\gcd (16,6)=2$.

After the second operation, we have the array $[4,0,6]$, and the maximum $\gcd$ is $\gcd (4,6)=2$.

Scoring

Solutions passing all test cases with $n,q\le 1000$ will be awarded at least $25$ points.

Solutions passing all test cases with $n,q\le 10000$ will be awarded at least $45$ points.