Pop və onun işçisi Balda haqqında nağıl
Bir gün keşiş və onun köməkçisi Balda oyun oynamağa qərar verdilər. Siz onlara kömək etməlisiniz. Bunun üçün adi kəsrin məxrəcini seçmək lazımdır, lakin kəsr qısaldılmayan olsa daha yaxşıdır. Həmçinin, müxtəlif surətlər üçün belə kəsrlərin sayı ən az olmalıdır.
Onlar yalnız keşişin seçdiyi ədədləri istifadə edə bilərlər. Əgər uyğun ədədlər bir neçə olarsa, Balda indeksi daha kiçik olan ədədi istəyir. Bəzən Balda massivdəki ədədləri istədiyi kimi dəyişir, buna görə də bunu nəzərə alın.
Giriş verilənləri
Birinci sətirdə massiv elementlərinin sayı N (1 ≤ N ≤ 1000000) verilir. Növbəti sətirdə boşluqla ayrılmış təbii ədədlər, yəni kəsrin məxrəcələri verilir. Hər biri on milyonu keçməyən bu ədədlər massivdə birdən nömrələnir. Üçüncü sətirdə M (1 ≤ M ≤ 100000) ədədi verilir. Bu, keşiş və Balda neçə dəfə oynamağı və ya massivi dəyişməyi planlaşdırdıqlarını göstərir. Sonra M sətir var, hər biri üç ədəd ehtiva edir və iki növ ola bilər: 1 X Y, burada 1 ≤ X ≤ Y ≤ N keşiş və Balda oynamağı planlaşdırdığı aralığın sərhədlərini göstərir; və ya 2 X Z, burada indeksli ədəd X 1 ≤ Z ≤ 10000000 ilə dəyişdirilir.
Çıxış verilənləri
Hər bir 1 X Y sorğusu üçün ayrıca sətirdə axtarılan məxrəc indeksini və onun dəyərini boşluqla ayıraraq çıxarmaq lazımdır.