Жила была девочка Женя. Как-то раз мама послала ее в магазин за баранками, но по дороге она нашла цветок, да не простой, а волшебный – Цветик-Семицветик, он выполнял любые желания. Как любая маленькая девочка, Женя загадала себе много-много игрушек, а именно n игрушек. Она пронумеровала места на полке от 1 до n и красиво расставила игрушки. Кроме того, для каждой игрушки она определила "красивость" - натуральное число, определяющее степень красоты игрушки. К Жене в гости часто приходят ее друзья, при этом, если приходит девочка, она называет два числа l и r, а затем Женя выбирает самую красивую игрушку из тех, что стоят на полочке на промежутке от l до r, и дарит ей. Если же приходит мальчик, он называет одно число v и дает свою игрушку с красивостью k, после чего Женя меняет его игрушку на ту, которая стоит на полочке с номером v. Если в какой-то момент девочка называет такие числа, что на этих местах нет ни одной игрушки, Женя, чтобы не расстроить ее, дарит ей самую красивую из всех, что у нее есть, если у нее совсем не осталось игрушек, выведите "O-o-ops". Если на промежутке несколько самых красивых игрушек, Женя выбирает игрушку с минимальным местом на полочке. Если в какой-то момент мальчик называет число, и в этом месте не оказывается игрушки, то он просто забирает обратно свою игрушку и сделка не состоится.
В первой строке находится количество игрушек n у Жени. Во второй строке расположены n (1 ≤ n ≤ 10^6) чисел a_i (1 ≤ a_i ≤ 10^9) - красивости игрушек . В третьей строке находится количество друзей m (1 ≤ m ≤ 10^5) у Жени. В следующих m строках находятся запросы друзей. Если к Жене пришла девочка, то первым будет символ "g", а затем два числа l и r. Если же мальчик, то первым символом будет "b", а затем два числа v и k.
Для каждой девочки выведите одно число - красивость игрушки, которую ей подарит Женя или "O-o-ops", если у нее игрушек нет.