Another query?...#181
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 integers . You need to process the following queries:
— assign each element on the segment [l;r] the value a_i := a_i , 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 .
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 and . For example, \gcd(12,16)=4 and \gcd(15,31)=1.
The first line contains two integers (1\le n\le 2\cdot 10^5) and (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 integers a_i (0\le a_i<2^{20}) — the array elements.
The next lines contain three integers each: , (1\le l\le r\le n) and (0\le x<2^{20}) — a description of the query.
Output q+1 lines — the answers to the queries of the second type.
Example 1
Example 2
Explanation for the first example:
Before performing any operations, we have the array [15,16,6], and the maximum is \gcd(15,6)=3.
After the first operation, we have the array [14,16,6], and the maximum 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 is \gcd(4,6)=2.
Solutions passing all test cases with n,q\le 1000 will be awarded at least points.
Solutions passing all test cases with n,q\le 10000 will be awarded at least points.