Query GCD su intervalli

Vi viene dato un array di n elementi e q query. Sono presenti due tipi di query: calcolare il massimo comun divisore (GCD) per un intervallo specifico e aggiornare il valore di un elemento in una determinata posizione. Il vostro obiettivo è gestire queste query in modo efficiente.

Input

La prima riga dell'input contiene due interi n e q (1 ≤ n, q ≤ 100 000), che rappresentano il numero di elementi nell’array e il numero di query.

La seconda riga contiene n interi separati da spazio, (), che costituiscono gli elementi iniziali dell’array.

Le successive q righe rappresentano ciascuna una query:

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

Output

Per ogni query di GCD su intervallo, stampate in una nuova riga il valore del GCD degli elementi nell’intervallo richiesto.

Esempi

Esempio di Input

Esempio di Output

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