Запросы на GCD по диапазону

Вам дан массив из n элементов и q запросов. Существуют два типа запросов: вычисление наибольшего общего делителя (НОД) для заданного диапазона и обновление элемента в определённой позиции. Ваша задача — эффективно обработать эти запросы.

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

Первая строка входа содержит два целых числа n и q (1 ≤ n, q ≤ 100000), обозначающих количество элементов в массиве и число запросов соответственно.

Вторая строка содержит n целых чисел, разделённых пробелами: (), которые являются начальными элементами массива.

В следующих q строках описаны запросы двух видов:

  • For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the GCD needs to be calculated.

  • For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .

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

Для каждого запроса на вычисление НОД по диапазону выведите полученное значение НОД элементов в указанном диапазоне в отдельной строке.

Примеры

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

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

6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6

4
2
2

Constraints

Time limit: 0.8 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue