#P14923. [UJGOI2023 Vidbir Day1]Another query?

[UJGOI2023 Vidbir Day1]Another query?

题目描述

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

给定一个长度为 nn 的整数数组 AA。你需要处理以下两类询问:

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

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

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

输入格式

第一行包含两个整数 nn(1≤n≤2⋅1051 \le n \le 2\cdot 10^5)和 qq(1≤q≤2⋅1051 \le q \le 2\cdot 10^5),分别表示数组长度和第一类询问数量。

第二行包含 nn 个整数 aia_i(0≤ai<2200 \le a_i < 2^{20})。

接下来 qq 行,每行包含三个整数 l,r,xl,r,x(1≤l≤r≤n1 \le l \le r \le n,0≤x<2200 \le x < 2^{20}),表示一次第一类询问。

输出格式

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

样例说明

第一组样例解释:

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

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

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

输入 #1

3 2
15 16 6
1 3 30
1 2 4

输出 #1

3
2
2

子任务

  • 正确通过 n,q≤1000n,q \le 1000 的所有测试点可获得至少 2525 分;
  • 正确通过 n,q≤10000n,q \le 10000 的所有测试点可获得至少 4545 分。

数据范围

1≤n,q≤2⋅1051 \le n,q \le 2\cdot 10^5,0≤ai,x<2200 \le a_i,x<2^{20}。