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