Seven-Colored Flower
Once upon a time, there was a girl named Zhenya. One day, her mother sent her to the store to buy bagels. On her way, she discovered a magical flower, the Seven-Color Flower, which could grant any wish. Like any little girl, Zhenya wished for many toys, specifically N toys. She numbered the spots on her shelf from 1 to N and arranged the toys neatly. For each toy, she assigned a "beauty" value, a natural number indicating how beautiful the toy is.
Zhenya's friends often visit her. When a girl visits, she specifies two numbers, l and r. Zhenya then selects the most beautiful toy from the shelf positions between l and r and gives it to her friend. If a boy visits, he specifies a position v and brings a toy with beauty k. Zhenya then swaps his toy with the one at position v on her shelf. If a girl requests toys from positions where none exist, Zhenya gives her the most beautiful toy she has. If she has no toys left, she outputs "O-o-ops". If there are multiple toys with the highest beauty in the range, Zhenya chooses the toy with the smallest position number. If a boy specifies a position with no toy, he simply takes his toy back, and no swap occurs.
Input
The first line contains a single number N – the number of toys Zhenya has. The second line contains N (1 ≤ N ≤ 10^6) numbers representing the beauty of each toy (1 ≤ A_i ≤ 10^9). The third line contains the number M (1 ≤ M ≤ 10^5) – the number of Zhenya's friends. The following M lines contain the requests from her friends. If a girl visits, the line starts with "g", followed by two numbers l and r. If a boy visits, the line starts with "b", followed by two numbers v and k.
Output
For each girl, output one number – the beauty of the toy Zhenya will give her, or "O-o-ops" if she has no toys left.