题目描述

所有选手都已经厌倦了询问题，但每场比赛至少都应该有一道这样的题。于是它来了……

给定一个长度为 $n$ 的整数数组 $A$。你需要处理以下两类询问：

• $l\ r\ x$：将区间 $[l,r]$ 中每个元素赋值为 $a_i := a_i\ \&\ x$，其中 $\&$ 表示按位与运算；
• ?：输出所有满足 $1 \le i < j \le n$ 且 $\min(a_i,a_j)>0$ 的点对中，$\gcd(a_i,a_j)$ 的最大值。若不存在这样的点对，输出 $0$。

输入中只会出现第一类询问。请你认为每次第一类询问之后都会紧接着一次第二类询问。此外，在第一类询问出现之前，也需要先输出一次第二类询问的答案。

这里 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。例如，$\gcd(12,16)=4$，$\gcd(15,31)=1$。

输入格式

第一行包含两个整数 $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,x$（$1 \le l \le r \le n$，$0 \le x < 2^{20}$），表示一次第一类询问。

输出格式

输出 $q+1$ 行，分别表示每次第二类询问的答案。

样例说明

第一组样例解释：

执行任何操作前，数组为 $[15,16,6]$，最大公约数为 $\gcd(15,6)=3$。

第一次操作后，数组为 $[14,16,6]$，最大公约数为 $\gcd(14,16)=\gcd(14,6)=\gcd(16,6)=2$。

第二次操作后，数组为 $[4,0,6]$，最大公约数为 $\gcd(4,6)=2$。

输入 #1

3 2
15 16 6
1 3 30
1 2 4

输出 #1

3
2
2

子任务

• 正确通过 $n,q \le 1000$ 的所有测试点可获得至少 $25$ 分；
• 正确通过 $n,q \le 10000$ 的所有测试点可获得至少 $45$ 分。

数据范围

$1 \le n,q \le 2\cdot 10^5$，$0 \le a_i,x<2^{20}$。