409469: GYM103567 H Осознание десятого уровня

H. Осознание десятого уровняограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Бендер «Сгибальщик» Родригез насмотрелся аниме, после чего решил приобщиться к японской культуре поплотнее. Для начала Бендер выбрал наиболее близкий ему род искусства  — «Оригами»: ведь тут всего лишь надо сгибать бумагу то туда, то сюда, он справится в два счёта.

Но, проведя дни за сгибанием и разгибанием листов бумаги, Бендер осознал всю глубину философии, лежащей за таким простым процессом. Теперь Бендер готов поделиться этим сакральным знанием с вами, не упустите свой шанс!(*)

Например, представьте перед собой прямоугольный лист бумаги... Представили? Мысленно согните его пополам справа-налево ровно посередине, затем пополам снизу-вверх, и, наконец, пополам слева-направо... Согнули? Кажется, что перед Вами все тот же прямоугольный лист бумаги, но он больше никогда не станет прежним... Развернув согнутый в несколько раз лист, Вы немедленно увидите следующую картину:

$$$\text{ }$$$

Полученную Вами следующей последовательностью сгибов:

$$$\text{ }$$$

$$$\text{ }$$$

$$$\text{ }$$$

Вы два раза согнули лист бумаги по вертикальной линии сгиба и один раз по горизонтальной линии сгиба, поэтому, получилась таблица из $$$6$$$ вертикальных сгибов и $$$4$$$ горизонтальных сгибов, направленных либо к Вам, обозначенных $$$U$$$ (от слова $$$\text{up}$$$), либо от Вас, обозначенных $$$D$$$ (от слова $$$\text{down}$$$).

Если Вы сделаете $$$m$$$ сгибов по вертикали и $$$n$$$ по горизонтали, то получится $$$2^n$$$ строк, в каждой из которых будет по $$$2^m-1$$$ вертикальных сгибов, и $$$2^m$$$ столбцов, в каждом из которых будет по $$$2^n-1$$$ горизонтальных сгибов.

Пронумеруем строки целыми числами от $$$1$$$ до $$$2^n$$$ сверху-вниз, а столбцы – целыми числами от $$$1$$$ до $$$2^m$$$ слева-направо. Вертикальные сгибы в каждой строке пронумеруем целыми числами от $$$1$$$ до $$$2^m-1$$$, а горизонтальные сгибы в каждой строке – целыми числами от $$$1$$$ до $$$2^n-1$$$. Сможете ли Вы для заданных сгибов сообщить, в какую сторону они направлены?

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ $$$\left(0 \le n \le 29, 0 \le m \le 29\right)$$$  — суммарное количество операций сгиба вдоль горизонтальных и вертикальных линий, соответственно.

В следующих $$$n+m$$$ строках заданы сами операции сгиба прямоугольного листа в хронологическом порядке:

• $$$\text{UD}$$$ или $$$\text{DU}$$$  — лист необходимо согнуть вдоль горизонтальной середины сверху-вниз или снизу-вверх, соответственно.
• $$$\text{LR}$$$ или $$$\text{RL}$$$  — лист необходимо согнуть вдоль вертикальной середины слева-направо или справа-налево, соответственно.

Затем дано целое число $$$q$$$ $$$\left(1 \le q \le 10^4\right)$$$  — количество запросов.

В следующих $$$q$$$ строках приведены сами запросы по одному в каждой строке:

• $$$v\text{ }r\text{ }i$$$ $$$\left(1 \le r \le 2^n, 1 \le i \le 2^m-1\right)$$$  — нужно сообщить, в какую сторону направлен вертикальный сгиб, находящийся в строке с номером $$$r$$$ и имеющий в ней номер $$$i$$$.
• $$$h\text{ }c\text{ }j$$$ $$$\left(1 \le c \le 2^m, 1 \le j \le 2^n-1\right)$$$  — нужно сообщить, в какую сторону направлен горизонтальный сгиб, находящийся в столбце с номером $$$c$$$ и имеющий в этом столбце номер $$$j$$$.

Выходные данные

Ответьте на все запросы в том порядке, в котором они даны. Выведите ответы в виде одной строки из $$$q$$$ символов, каждый из которых либо $$$U$$$, либо $$$D$$$.

ПримерыВходные данные

1 2
RL
DU
LR
10
v 1 1
v 1 2
v 1 3
v 2 1
v 2 2
v 2 3
h 1 1
h 2 1
h 3 1
h 4 1

Выходные данные

DDUUDDDDUU

Входные данные

2 2
LR
UD
DU
RL
24
v 1 1
v 1 2
v 1 3
v 2 1
v 2 2
v 2 3
v 3 1
v 3 2
v 3 3
v 4 1
v 4 2
v 4 3
h 1 1
h 1 2
h 1 3
h 2 1
h 2 2
h 2 3
h 3 1
h 3 2
h 3 3
h 4 1
h 4 2
h 4 3

Выходные данные

UDDDDUUDDDDUDUUDUUUDDUDD

Примечание

$$$\textbf{Важная информация по языку Python}$$$: команда языка input() при чтении строк возвращает строку вместе с символом перевода строки на конце. Советуем использовать комбинацию input().strip() для чтения строк в данной задаче.

Пояснения к примерам:

Первый тестовый пример полностью соответствует рисунку из условия.

Второй тестовый пример:

(*) - услуга осознания тарифицируется посекундно, стоимость зависит от порядка сгибов и количества запросов, а так же взаимного расположения галактик «Млечный Путь» и «Туманность Андромеды».