Бендер «Сгибальщик» Родригез насмотрелся аниме, после чего решил приобщиться к японской культуре поплотнее. Для начала Бендер выбрал наиболее близкий ему род искусства — «Оригами»: ведь тут всего лишь надо сгибать бумагу то туда, то сюда, он справится в два счёта.
Но, проведя дни за сгибанием и разгибанием листов бумаги, Бендер осознал всю глубину философии, лежащей за таким простым процессом. Теперь Бендер готов поделиться этим сакральным знанием с вами, не упустите свой шанс!(*)
Например, представьте перед собой прямоугольный лист бумаги... Представили? Мысленно согните его пополам справа-налево ровно посередине, затем пополам снизу-вверх, и, наконец, пополам слева-направо... Согнули? Кажется, что перед Вами все тот же прямоугольный лист бумаги, но он больше никогда не станет прежним... Развернув согнутый в несколько раз лист, Вы немедленно увидите следующую картину:
$$$\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() для чтения строк в данной задаче.
Пояснения к примерам:
Первый тестовый пример полностью соответствует рисунку из условия.
Второй тестовый пример:
(*) - услуга осознания тарифицируется посекундно, стоимость зависит от порядка сгибов и количества запросов, а так же взаимного расположения галактик «Млечный Путь» и «Туманность Андромеды».
