Задачи
Ожерелья
Ожерелья
Алиса: "\textit{У меня было самое красивое ожерелье. Слева направо, оно состояло из двух красных бусин, двух зелёных и ещё одной красной}".
Биатрисс быстро нашла, что ответить: "\textit{А моё было ещё лучше. Оно выглядело почти как твоё, если убрать две самые правые бусины и добавить вместо них две голубых}".
Как только она закончила говорить, в обсуждение быстро вступила Каролина: "\textit{Оно почти как моё. Только у него есть ещё одна бусина слева}".
Вы, наверное, уже не удивитесь, когда я вам скажу, что Доминика тоже не осталась в стороне. "\textit{Все ваши ожерелья такие скучные. Чтобы получить моё, надо взять ожерелье Биатрисс, убрать самую левую и самую правую бусину, и добавить две чёрных слева}".
И это продолжалось, пока Заида не спросила: "\textit{Я немного запуталась. Какого цвета была самая левая бусина в ожерелье Евегении?}" На этот вопрос никто не смог ответить.
Может быть, вы поможете девушкам?
Ваша программа должна уметь обрабатывать множество ожерелий. Ожерелье - это последовательность целых чисел от \textbf{0} до \textbf{1000000}, упорядоченных слева направо. У каждого ожерелья есть номер. Изначально есть одно пустое ожерелье. Оно имеет номер \textbf{0}. Далее вам поступает не более \textbf{1000001} запросов.
Запросы бывают следующих типов.
\begin{itemize}
\item \textbf{A id side color} - Этот запрос означает, что надо создать новое ожерелье из ожерелья с номером \textbf{id} путём добавления бусины цвета \textbf{color} со стороны \textbf{side}. Параметр \textbf{side} - это буква \textbf{L}, если надо добавить бусину слева, и \textbf{R}, если справа. Номер нового ожерелья на \textbf{1} больше самого большого из уже существующих номеров. Гарантируется, что ожерелье с номером \textbf{id} уже существует.
\item \textbf{R id side} - Этот запрос означает, что надо создать новое ожерелье из ожерелья с номером \textbf{id} путём удаления бусины со стороны \textbf{side}. Сторона задаётся аналогично первому запросу. Номер нового ожерелья на \textbf{1} больше самого большого из уже существуюших номеров. Гарантируется, что ожерелье с номером \textbf{id} уже существует и не является пустым.
\item \textbf{Q id side} - В качестве ответа на этот запрос надо вывести одно число - цвет бусины со стороны \textbf{side} в ожерелье \textbf{id}. Гарантируется, что оно существует и не явлется пустым.
\item \textbf{X} - Этот запрос означает, что нужно завершить выполнение программы.
\end{itemize}
\InputFile
На вход вашей программе подаётся последовательность запросов в описанном выше формате. Количество запросов не превосходит \textbf{10^6+1}.
\OutputFile
В ответ на каждый запрос типа \textbf{Q} выведите ответ на него в отдельной строке.
Входные данные #1
A 0 L 1 A 1 L 2 Q 2 R R 2 R Q 3 R Q 2 R X
Выходные данные #1
1 2 1