eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Намиста

Намиста

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

Аліса: "У мене було саме красиве намисто. Зліва направо, воно складалось з двох червоних намистин, двох зелених і ще однієї червоної".

Біатрисс швидко знайшла, що відповісти: "А моє було ще кращим. Воно виглядало майже як твоє, якщо забрати дві самі праві намистини і додати замість них дві голубі".

Як тільки вона закінчила говорити, у обговорення швидко вступила Кароліна: "Воно майже як моє. Тільки у нього є ще одна намистина ліворуч".

Ви, напевне, вже не здивуєтесь, коли я вам скажу, що Домініка також не залишилась осторонь. "Усі ваші намиста такі скучні. Щоб отримати моє, потрібно взяти намисто Біатрисс, забрати саму ліву та саму правую намистини, і додати дві чорних ліворуч".

І це продовжувалось, доки Заїда не запитала: "Я трохи заплуталась. Якого кольору була сама ліва намистина у написті Євегенії?" На це запитання ніхто не зміг відповісти.

Можливо ви допоможете дівчатам?

Ваша програма повинна вміти опрацьовувати множину намист. Намисто - це послідовність цілих чисел від 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 виведіть відповідь на нього у окремому рядку.

Приклад

Вхідні дані #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