Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Exceptional Artist

By ishtupeed · Limits 1s, 64 MB

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.

Input

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).

Output

For any operations of type 1, 3, and 4, print the output as specified. Output for each operation should be separated by a newline.

Sample

InputOutput
5
2 3 G
2 4 B
2 5 R
1 5
3 4
R
5

Discussion

Statistics


75% Solution Ratio

aaman007Earliest, Feb '20

EgorKulikovFastest, 0.2s

ashikurrahmanLightest, 14 MB

jaberndcShortest, 682B

Submit

Login to submit

Editorial

Consider (x, c) as a pair, where x is the positive integer denoting the position of a pixel in the s...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.