Намиста

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

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

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

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

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

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

Ваша програма повинна вміти опрацьовувати множину намист. Намисто — це послідовність цілих чисел від $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 — Цей запит означає, що потрібно завершити виконання програми.