Consultas de GCD em Intervalos

Temos um array de n elementos e q consultas. Existem dois tipos de consultas: calcular o maior divisor comum (GCD) num intervalo específico e atualizar um elemento em determinada posição. O seu objetivo é processar estas consultas de forma eficiente.

Entrada

A primeira linha da entrada contém dois inteiros n e q (1 ≤ n, q ≤ 100 000), que representam a quantidade de elementos no array e o número de consultas, respetivamente.

A segunda linha contém n inteiros separados por espaços (), que são os valores iniciais do array.

As q linhas seguintes descrevem cada consulta:

• 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 .

Saída

Para cada consulta de GCD em intervalo, imprima numa linha separada o valor do GCD correspondente aos elementos desse intervalo.

Exemplos