D. Баш и сложная математическая головоломка
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Баш любит играть с массивами. У него есть массив a1, a2, ... an, состоящий из n целых чисел. Он любит делать предположения о значении наибольшего общего делителя (gcd) на некоторых подотрезках массива. Конечно же, его предположения не всегда верны, но Баш будет доволен, если его предположение почти верно.

Допустим он предположил, что gcd элементов на подотрезке [l, r] массива a равен x. Тогда он считает предположение почти верным если если он может изменить не более одного элемента на подотрезке так, что gcd на этом отрезке станет равным x. Учтите, что после предположения о значении gcd Баш не меняет сам массив, ему только интересно, можно ли сделать так, чтобы gcd на подотрезке стал равен x. Помимо этого, Баш иногда изменяет сам массив.

Помогите Башу определить, какие его догадки являются почти верными. Формально, Вам надо обработать q запросов, каждый из которых имеет один из двух типов:

  • 1 l r x — Баш предполагает, что gcd на подотрезке [l, r] равен x. Сообщите, правда ли, что это предположение почти верно.
  • 2 i y — Баш изменяет значение ai на y.

Массив индексируется, начиная с 1.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 5·105) — размер массива.

Во второй строке содержатся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива.

В третьей строке содержится целое число q (1 ≤ q ≤ 4·105) — количество запросов.

В следующих q строках содержатся описания запросов. Каждый запрос представляется в одном из следующих форматов:

  • 1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109).
  • 2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 109).

Гарантируется, что в тесте есть хотя бы один запрос первого типа.

Выходные данные

Для каждого запроса первого типа выведите "YES" (без кавычек), если предположение Баша верно и "NO" (без кавчек) иначе.

Примеры
Входные данные
3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2
Выходные данные
YES
YES
NO
Входные данные
5
1 2 3 4 5
6
1 1 4 2
2 3 6
1 1 4 2
1 1 5 2
2 5 10
1 1 5 2
Выходные данные
NO
YES
NO
YES
Примечание

В первом тестовом примере изначальное состояние массива таково: {2, 6, 3}

Для запроса 1 gcd первых двух элементов массива уже равен 2.

Для запроса 2 можно добиться gcd равного 3 изменив значение первого элемента на 3. Учтите, что после запросов типа 1 массив не изменяется.

После запроса 3 массив выглядит так: {9, 6, 3}.

В запросе 4 нельзя изменить один элемент так, чтобы получить gcd, равный 2.