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

İndi Vitinin bir proqramı var ki, ona çox sayda ədədlərin ƏBOB-unu tez tapmağa kömək edir. Buna görə də mühafizəçilər qaydaları dəyişməyə qərar verdilər: indi Viti $[l;r]$ intervalındakı ədədlərin ən böyük ortaq bölənini (ƏBOB) tapmalıdır, mühafizəçilər isə ən kiçik ortaq böləni (ƏKOB) tapmalıdırlar. Kimin ədədi kiçikdirsə, o da qalib gəlir.

Giriş verilənləri

Birinci sətir massivdəki elementlərin sayını $n(1\le n\le 10^6)$ ehtiva edir. İkinci sətirdə $n$ ədəd var — massiv elementləri $a_i(1\le a_i\le 10^9)$. Üçüncü sətirdə sorğuların sayı $m(1\le m\le 10^5)$ verilir. Sonra $m$ sətirdə üç ədəd $q,l,r(1\le l\le r\le n)$ verilir. Əgər $q=1$, $[l;r]$ intervalı üçün qalibi müəyyən etmək 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ı-ayrı sətirdə "wins" sətirini çıxarın, əgər Viti qalib gəldisə, "loser" sətirini çıxarın, əgər o uduzdusa və "draw" sətirini çıxarın, əgər heç-heçə olduysa.

Nümunələr