Tasks of past championships

"A" Сгибание ленточки / Финал RCC 2015
Time limit None
Memory limit None

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

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

Input format

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

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

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

Output format

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

Examples
Input data
3
1
R
1
1
2
LR
3
1 2 3
3
LRL
7
1 2 3 4 5 6 7
Output data
D
U
D
D
D
U
U
D
D
D
U
 

Log in

We have launched a unified system of registration for the Mail.Ru Group championships.
Sign in using your username and password or register russiancodecup.ru single sign-on portal.
After registration you will be redirected back.

Go to

The instruction for password recovery has been sent to your email