Знову запити?...#11363
Всі учасники дуже втомилися від задач на запити, але кожен контест повинен мати хоча б одну таку задачу. Ось і вона...
Вам дано масив цілих чисел довжини . Потрібно обробляти наступні запити:
— для кожного елемента на відрізку [l; r] присвоїти a_i := a_i \& x, де — знак побітового AND.
— вивести максимальне значення \gcd(a_i, a_j) для всіх пар 1 \le i < j \le n із \min(a_i, a_j) > 0. Якщо таких пар немає, виведіть .
У вхідних даних будуть лише запити першого типу. Вважайте, що після кожного запиту першого типу йде запит другого типу. Також перед першим запитом першого типу треба вивести відповідь на запит другого типу.
Тут \gcd(a, b) означає найбільший спільний дільник чисел і . Наприклад, \gcd(12, 16) = 4, а \gcd(15, 31) = 1.
Перший рядок містить два цілі числа (1 \le n \le 2 \cdot 10^5) і (1 \le q \le 2 \cdot 10^5) — розмір масиву і кількість запитів першого типу.
Наступний рядок містить цілих чисел a_i (0 \le a_i < 2^{20}) — елементи масиву.
Далі йдуть рядків, кожен з яких містить три цілі числа , (1 \le l \le r \le n), та (0 \le x < 2^{20}) — опис запиту.
Виведіть q+1 рядок — відповіді на запити другого типу.
Example 1
Example 2
Пояснення до першого прикладу:
До виконання операцій першого типу масив дорівнює [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.
Рішення, які правильно працюють для n, q \le 1000, набиратимуть принаймні балів.
Рішення, які правильно працюють для n, q \le 10000, набиратимуть принаймні балів.