Qış üçün ehtiyatlar

Kirpi Alina alma bankalarını anbarında yerləşdirməklə bağlı təcrübələrini davam etdirir. Bu dəfə o, problemi tamamilə yeni bir üsulla həll etməyə qərar verərək, bankaların sırasını tamamilə dəyişə bilən bir avtomat icad etdi. İndi Alina bu avtomatın işini modelləşdirmək istəyir.

Giriş məlumatları:

Birinci sətirdə N - Alinanın sahib olduğu bankaların sayı verilir. (N ≤ 10^5)

İkinci sətirdə boşluqla ayrılmış N ədəd - müvafiq bankalardakı almaların keyfiyyətləri göstərilir.

Növbəti sətirdə M - avtomata olan sorğuların sayı verilir (M ≤ 5∙10^5).

Sonrakı hər sətirdə iki növ sorğudan biri təsvir olunur:

1. L, R - çevriləcək aralıq (0 ≤ L < R ≤ N-1).

2. X - X mövqeyindəki almaların keyfiyyəti haqqında sorğu (0 ≤ X ≤ N-1).

Çıxış məlumatları:

İkinci tip sorğuların hər birinə cavabı ayrı sətirdə verin.