22049번 - Сгибание ленточки 다국어

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

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

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

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

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

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