Задания прошлых чемпионатов

"A" Сгибание ленточки / Финал RCC 2015
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Из клетчатой бумаги вырезали полоску размером 1×2n. Затем ее положили горизонтально на стол и n раз согнули ровно пополам, каждый раз либо левую половину клали поверх правой (назовем это «левый поворот»), либо правую поверх левой (назовем это «правый поворот»). В итоге получилась стопка квадратиков 1×1. После этого полоску развернули обратно и положили на стол той же стороной, которой она лежала изначально.

Ваша задача теперь состоит в том, чтобы быстро отвечать на запросы, в какую сторону ориентирован i-й сгиб полоски, находящийся между i-м и i+1-м квадратиками 1×1, считая слева.

Формат входных данных

Первая строка входных данных содержит одно число t (1 ≤ t ≤ 100) — количество тестов. Далее следуют описания тестов. Каждый тест задается следующим образом: первая строка содержит число n (1 ≤ n ≤ 60) — количество сгибов полоски. Следующая строка теста содержит строку из n символов, каждый из которых описывает левый или правый повороты соответственно (символ «L» описывает левый поворот, а «R» — правый).

В следующей строке теста содержится число q (1 ≤ q ≤ 105) — количество запросов. Затем через пробел идут сами запросы, каждый из которых представляется одним числом i (1 ≤ i ≤ 2n −1) — номер сгиба, ориентацию которого требуется узнать.

Гарантируется, что суммарное количество запросов не превосходит 105.

Формат выходных данных

На каждый запрос выведите «U», если сгиб ориентирован вверх, и «D», если сгиб ориентирован вниз.

Примеры
Входные данные
3
1
R
1
1
2
LR
3
1 2 3
3
LRL
7
1 2 3 4 5 6 7
Выходные данные
D
U
D
D
D
U
U
D
D
D
U
 

Вход

Мы запустили единую систему регистрации для чемпионатов Mail.Ru Group.
Авторизуйтесь, используя ваш логин и пароль от russiancodecup.ru или зарегистрируйтесь на портале единой регистрации.
После регистрации вы будете перенаправлены назад.

Перейти

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.