Consultas de GCD en rango

Se te proporciona un array de n elementos y q consultas. Existen dos tipos de consultas: calcular el greatest common divisor (GCD) para un rango específico y actualizar un elemento en una posición determinada. Tu objetivo es procesar estas consultas de manera eficiente.

Entrada

La primera línea de la entrada contiene dos enteros n y q (1 ≤ n, q ≤ 100 000), que representan la cantidad de elementos en el array y el número de consultas, respectivamente.

La segunda línea incluye n enteros separados por espacios (), que son los elementos iniciales del array.

Las siguientes q líneas describen 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 .

Salida

Por cada consulta de GCD en rango, imprime en una línea separada el GCD de los elementos dentro del rango solicitado.

Ejemplos

Entrada

Salida

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