Wstęp do programowania w C++

W Dwójkolandii przyszedł czas na długo wyczekiwane wybory. Okręgi wyborcze wystawiły swoich kandydatów, a wyborcy zapoznali się z ich planami wyborczymi. Dziś jest dzień wyborów, a ty zostałeś powołany na wolontariat polegający na zliczaniu głosów i określeniu, czy w danym okręgu wyborczym jakiś kandydat osiągnął więcej niż 50% głosów. System wyborczy w Dwójkolandii działa następująco. Wyborcy należący do danego okręgu wyborczego są zapisani na spójnej liście, jeden za drugim, itd. Wszystkie listy połączone są w jedną wielką listę. Dodatkowo każdy wyborca ma prawo zmienić swój wybór i zaznaczyć innego kandydata - taki system :). Ty jednak jesteś bardzo sprytną osobą i pojąłeś trudną sztukę programowania. Napisz program, który znacznie ułatwi ci pracę na wolontariacie, wyznaczający lidera w przedziale liczb. Wykonujemy dwie operacje. Pierwsza, to zmiana wyboru kandydata na inny (zmiana decyzji wyborcy), druga to sprawdzenie, czy w okręgu zaczynającym się od wyborcy na pozycji a a kończącym się na wyborcy na pozycji b został wybrany kandydat do rządzenia Dwójkolandią - tzn. liczba oddanych głosów na tę osobę jest większa niż 50%.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę wyborców (nie więcej niż 10⁶).

W drugim wierszu n liczb naturalnych określających głosy wyborców. Każdy kandydat jest reprezentowany przez liczbę mieszczącą się w przedziale [0..10⁹]. Jeden kandydat może być wybierany w kilku okręgach (taki system :)).

W trzecim wierszu jedna liczba q określająca liczbę zapytań (nie więcej niż 10⁶).

Specyfikacja każdego zapytania:

najpierw jeden znak i lub q, następnie dwie liczby całkowite. Jeśli pojawi się i, zostaną podane dwie liczby całkowite x i y, oznaczające, że należy podmienić decyzję wyborcy z pozycji x w ciągu na y, natomiast, gdy pojawi się znak q, to pojawią się dwie liczby a i b, definiujące przedział [a...b], w którym należy określić, czy występuje lider w tym przedziale (1 ≤ x ≤ n, 0 ≤ y ≤ 10⁹, 1 ≤ a ≤ b ≤ n).

Wyjście

Dla każdego zapytania, w którym wystąpiła litera q należy wypisać lidera zbioru w przedziale [a..b], lub napis brak, gdy lider nie występuje.

Przykład

Wejście:
6
2 2 3 2 7 8
5
q 1 4
q 1 1
i 3 7
q 3 5
q 3 6


Wyjście:
2
2
7
brak