Алиса: "\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} выведите ответ на него в отдельной строке.