Nel paese delle lezioni non apprese#4481
Victor si ritrovò in una terra di lezioni non apprese. Per tornare a casa, deve completare vari compiti. Uno di questi compiti prevede di sconfiggere una guardia in un gioco del MCD. Le regole sono semplici: dato un array di numeri interi positivi, i giocatori selezionano due numeri e , e trovano il massimo comun divisore (MCD) di tutti gli elementi dell'array dall'indice all'indice incluso. Il giocatore che trova il MCD più velocemente vince. Per prevenire giochi scorretti, alcuni numeri nell'array possono essere occasionalmente sostituiti.
Victor è desideroso di tornare a casa. Aiutalo scrivendo un programma che possa calcolare rapidamente il MCD su un intervallo specificato.
La prima riga contiene il numero di elementi n~(1 \le n \le 10^5) nell'array. La seconda riga contiene numeri interi — gli elementi a_i~(1 \le a_i \le 10^9) dell'array. La terza riga fornisce il numero di query m~(1 \le m \le 10^5). Ciascuna delle successive righe contiene tre numeri interi q, l, r~(1 \le l \le r \le n).
Se q = 1, trova il MCD degli elementi nell'intervallo [l, r];
Se q = 2, cambia l'elemento in posizione con il numero .
Per ogni query con numero stampa la risposta su una riga separata.
Esempio 1