Намиста
Аліса: "У мене було саме красиве намисто. Зліва направо, воно складалось з двох червоних намистин, двох зелених і ще однієї червоної".
Біатрисс швидко знайшла, що відповісти: "А моє було ще кращим. Воно виглядало майже як твоє, якщо забрати дві самі праві намистини і додати замість них дві голубі".
Як тільки вона закінчила говорити, у обговорення швидко вступила Кароліна: "Воно майже як моє. Тільки у нього є ще одна намистина ліворуч".
Ви, напевне, вже не здивуєтесь, коли я вам скажу, що Домініка також не залишилась осторонь. "Усі ваші намиста такі скучні. Щоб отримати моє, потрібно взяти намисто Біатрисс, забрати саму ліву та саму правую намистини, і додати дві чорних ліворуч".
І це продовжувалось, доки Заїда не запитала: "Я трохи заплуталась. Якого кольору була сама ліва намистина у написті Євегенії?" На це запитання ніхто не зміг відповісти.
Можливо ви допоможете дівчатам?
Ваша програма повинна вміти опрацьовувати множину намист. Намисто - це послідовність цілих чисел від 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 виведіть відповідь на нього у окремому рядку.