Баш любит играть с массивами. У него есть массив 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.
Выходные данные
Для каждого запроса первого типа выведите "YES" (без кавычек), если предположение Баша верно и "NO" (без кавчек) иначе.
Примечание
В первом тестовом примере изначальное состояние массива таково: {2, 6, 3}
Для запроса 1 gcd первых двух элементов массива уже равен 2.
Для запроса 2 можно добиться gcd равного 3 изменив значение первого элемента на 3. Учтите, что после запросов типа 1 массив не изменяется.
После запроса 3 массив выглядит так: {9, 6, 3}.
В запросе 4 нельзя изменить один элемент так, чтобы получить gcd, равный 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2
|
YES
YES
NO
|
|
2
|
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
|