Necklaces

Alice said, I had the most beautiful necklace. From left to right, it consisted of two red beads, two green ones, and another red one.

Beatrice quickly responded, And mine was even better. It looked almost like yours, except you remove the two rightmost beads and add two blue ones instead.

Carolina then joined the conversation, It's almost like mine. Only it has one more bead on the left.

Not to be left out, Dominica added, All your necklaces are so boring. To get mine, you need to take Beatrice's necklace, remove the leftmost and rightmost beads, and add two black ones on the left.

This continued until Zaida asked, I'm a bit confused. What color was the leftmost bead in Eugenia's necklace? No one could answer her question.

Can you help the girls figure it out?

Your task is to process a series of queries related to necklaces. A necklace is represented as a sequence of integers from $0$ to $1000000$, arranged from left to right. Each necklace is assigned a unique number. Initially, there is one empty necklace, numbered $0$. You will receive up to 10^6+1 queries.

The queries are as follows:

• A $id$ $side$ $color$ — Create a new necklace from the necklace numbered $id$ by adding a bead of color $color$ to the side $side$. The side is specified as $L$ for left or $R$ for right. The new necklace is numbered one more than the current highest number. The necklace with number $id$ is guaranteed to exist.

• R $id$ $side$ — Create a new necklace from the necklace numbered $id$ by removing a bead from the side $side$. The side is specified similarly to the first query. The new necklace is numbered one more than the current highest number. The necklace with number $id$ is guaranteed to exist and is not empty.

• Q $id$ $side$ — Output the color of the bead on the side $side$ of the necklace numbered $id$. The side is specified as in the previous queries. The bead is guaranteed to exist and the necklace is not empty.

• X — Terminate the program.