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

Entrada

Saída

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