Irtiza is an extraordinary sketch artist. His obsession with perfection drives him to make every pixel of his sketch flawless. He goes through his sketch drawing pixel-by-pixel with immaculate precision. To assist in his pursuit of perfection, he is currently in the market for a drawing tab. He has some weird specifications for it.
For simplicity, consider the drawing tab as a one-dimensional line. Each pixel of the line is represented by a pair (x, c), where x is a positive integer denoting the position of the pixel on the screen, and c ∈ {R, G, B} is the set of colors. Note that each position can be assigned up to three colors, e.g., (5, R), (5, G), and (5, B) can co-exist in a single pixel, but there cannot be more than one (5, R). Initially, no color is assigned to any pixel.
Irtiza needs the tab to support the following operations:
1 x: Show the colors at position x on the screen. The colors shown should be in lexicographical order without any space in between. If no color is assigned to x yet, show 0.2 x c: Assign color c to position x. If x already has color c, then do nothing. You do not need to show anything for this type of operation.3 x: Show the position xn of the next colored pixel that appears after x in the line of pixels. That means, find the minimum xn (> x) that is assigned at least 1 color. If no such xn exists, show 0.4 x: Show the position xp of the previous colored pixel that appears before x in the line of pixels. That means, find the maximum xp (< x) that is assigned at least 1 color. If no such xp** exists, show 0.Now being a good friend of Irtiza, your task is to design a system that can handle such queries.
The input starts with a single integer Q (1 ≤ Q ≤ 3×105) denoting the number of operations to be performed. Each of the next Q lines contain a single operation as 1 x, 2 x c, 3 x, or 4 x (1 ≤ x ≤ 1018).
For any operations of type 1, 3, and 4, print the output as specified. Output for each operation should be separated by a newline.
| Input | Output |
|---|---|
5 2 3 G 2 4 B 2 5 R 1 5 3 4 | R 5 |