| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Из клетчатой бумаги вырезали полоску размером 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
Contest > Russian Code Cup > 2015 > RCC 2015 Final Round A번