Квітка-Семибарвка
Жила була дівчинка Женя. Якось мама відправила її до магазину за бубликами, але по дорозі вона знайшла квіточку, да не просту, а чарівну – Квіточку-Семибарвочку, вона виконувала любі бажання. Як усяка маленька дівчинка, Женя загадала собі багато-багато іграшок, а саме N іграшок. Вона пронумерувала місця на поличці від 1 до N і гарно розставила іграшки. Крім того, для кожної іграшки вона визначила "красивість" - натуральне число, яке визначає степінь краси іграшки. До Жені у гості часто приходять її друзі, при цьому, якщо приходить дівчинка, вона називає два числа l та r, а потім Женя вибирає саму красиву іграшку серед тих, що стоять на поличці на проміжку від l до r, і дарує їй. Якщо ж приходить хлопчик, він називає одне число v і дає свою іграшку з красивістю k, після чого Женя міняє його іграшку на ту, яка стоїть на поличці з номером v. Якщо у якийсь момент дівчинка називає такі числа, що на цих місцях немає жодної іграшки, Женя, щоб не засмутитиь її, дарить їй саму красиву з усіх, що у неї є, якщо ж у неї зовсім не залишилось іграшок, виведіть "O-o-ops". Якщо на проміжку декілька самих красивих ігрушок, то Женя вибирає іграшку з мінімальним місцем на поличці. Якщо у якийсь момент хлопчик називає число, і у цьому місці не виявляється іграшки, то він просто забирає назад свою іграшку і обмін не відбудеться.
Вхідні дані
У першому рядку єдине число N – кількість іграшок у Жені. У другому рядку N (1 ≤ N ≤ 10^6) чисел – красивості іграшок (1 ≤ A_i ≤ 10^9). У третьому рядку знаходиться число M (1 ≤ M ≤ 10^5) – кількість друзів Жені. У наступних M рядках знаходяться запити друзів. Якщо до Жені прийшла дівчинка, то першим буде символ "g", а потім два числа l та r. Якщо ж хлопчик, то першим символом буде "b", а потім два числа v та k.
Вихідні дані
Для кожної дівчинки виведіть одне число – красивість іграшки, яку їй подарує Женя або "O-o-ops", якщо у неї іграшок немає.