Öyrənilməmiş dərslər ölkəsində

Vitya öyrənilməmiş dərslər ölkəsinə düşüb. Evə qayıtmaq üçün o, bir sıra tapşırıqları yerinə yetirməlidir. Bu tapşırıqda o, gözətçiləri ƏBOB-oyununda məğlub etməlidir. Oyunun qaydaları çox sadədir: təbii ədədlərdən ibarət bir massiv verilir, sonra oyunçular iki ədəd $l$ və $r$ seçirlər və onlardan massivdə $l$-dən $r$-ə qədər olan indekslərdəki bütün elementlərin ən böyük ortaq bölənini (ƏBOB) hesablamaq tələb olunur. Kim daha tez hesablayarsa, o qalib gəlir. Ədalətsiz oyunlardan qaçmaq üçün bəzən massivdəki bəzi ədədləri başqaları ilə dəyişirlər.

Vitya evə qayıtmaq istəyir, ona kömək edin və verilmiş aralıqda ƏBOB-u çox tez hesablaya bilən bir proqram yazın.

Giriş verilənləri

Birinci sətir massivdəki elementlərin sayını $n(1\le n\le 10^5)$ ehtiva edir. İkinci sətirdə $n$ ədəd $a_i(1\le a_i\le 10^9)$ - massiv elementləri verilir. Üçüncü sətirdə sorğuların sayı $m(1\le m\le 10^5)$ göstərilir. Daha sonra $m$ sətirdə üç ədəd $q,l,r(1\le l\le r\le n)$ verilir.

• Əgər $q=1$, onda $[l,r]$ aralığındakı elementlərin ƏBOB-unu hesablamaq lazımdır;

• Əgər $q=2$, onda $l$ mövqeyindəki elementi $r$ ədədi ilə əvəz etmək lazımdır.

Çıxış verilənləri

Hər bir $1$ nömrəli sorğu üçün ayrıca sətirdə sorğunun cavabını verin.

Nümunələr