B. Странная установка
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ установок, расположенных по кругу, где $$$n$$$ не превосходит $$$20$$$. Каждая установка является либо типа A, либо типа B. Установки пронумерованы по часовой стрелке от $$$1$$$ до $$$n$$$, и тип $$$i$$$-й установки обозначается как $$$s_i$$$. Каждая установка принимает целое число $$$x$$$ и обновляет его в зависимости от своего типа:

  • Тип A: Уменьшить $$$x$$$ на $$$1$$$. Формально, обновить $$$x := x - 1$$$.
  • Тип B: Заменить $$$x$$$ на целую часть половины его значения. Формально, обновить $$$x := \left\lfloor\frac{x}{2}\right\rfloor$$$, где $$$\lfloor y\rfloor$$$ обозначает округление вниз значения $$$y$$$ до ближайшего целого числа, то есть наибольшее целое число, не превосходящее $$$y$$$.

Вам даны $$$q$$$ запросов, каждый из которых состоит из одного целого числа $$$a$$$. В каждом запросе вы начинаете с установки $$$1$$$, имея целое число $$$a$$$. Каждую секунду происходят следующие два действия по порядку:

  1. Текущая установка обновляет $$$a$$$ в зависимости от своего типа.
  2. Затем вы перемещаетесь на один шаг по часовой стрелке к следующей установке. Формально
    • Если вы находитесь на установке $$$i$$$, где $$$1 \le i \le n - 1$$$, переместитесь к установке $$$i + 1$$$.
    • Если вы находитесь на установке $$$n$$$, переместитесь к установке $$$1$$$.

Этот процесс продолжается до тех пор, пока ваше целое число $$$a$$$ не станет $$$0$$$. Для каждого запроса определите количество секунд до того, как $$$a$$$ станет $$$0$$$.

Обратите внимание, что все запросы независимы друг от друга.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1\le n\le 20$$$, $$$1\le q\le 10^4$$$) — количество установок и количество запросов соответственно.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ ($$$|s| = n$$$ и $$$s_i = \mathtt{A} \text{ или }\mathtt{B}$$$) — типы установок.

Третья строка каждого набора входных данных содержит $$$q$$$ целых чисел $$$a_1, a_2, \ldots, a_q$$$ ($$$1\le a_i\le 10^9$$$) — начальное целое число для каждого запроса.

Обратите внимание, что нет дополнительного ограничения на сумму $$$n$$$ по всем наборам входных данных.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответы на каждый запрос.

Пример
Входные данные
3
2 2
BA
3 4
1 1
B
20
6 4
BAABBA
2 8 32 95
Выходные данные
2
3
5
2
5
8
11
Примечание

В первом наборе входных данных запросы следующие:

  • Запрос $$$1$$$: $$$a = 3$$$
    1. Начните на установке $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{3}{2}\right\rfloor = 1$$$.
    2. Переместитесь на установку $$$2$$$. Установка $$$2$$$ уменьшает $$$a$$$ на $$$1$$$. Теперь $$$a = 1 - 1 = 0$$$.
    Следовательно, требуется $$$2$$$ секунды, чтобы $$$a$$$ достигло $$$0$$$.
  • Запрос $$$2$$$: $$$a = 4$$$
    1. Начните на установке $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{4}{2}\right\rfloor = 2$$$.
    2. Переместитесь на установку $$$2$$$. Установка $$$2$$$ уменьшает $$$a$$$ на $$$1$$$. Теперь $$$a = 2 - 1 = 1$$$.
    3. Вернитесь к установке $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$.
    Следовательно, требуется $$$3$$$ секунды, чтобы $$$a$$$ достигло $$$0$$$.

Во втором наборе входных данных есть только один запрос с $$$a = 20$$$:

  1. Начните на установке $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{20}{2}\right\rfloor = 10$$$.
  2. Переместитесь на установку $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{10}{2}\right\rfloor = 5$$$.
  3. Переместитесь на установку $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{5}{2}\right\rfloor = 2$$$.
  4. Переместитесь на установку $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{2}{2}\right\rfloor = 1$$$.
  5. Переместитесь на установку $$$1$$$. Установка $$$1$$$ заменяет $$$a$$$ на целую часть половины его значения. Теперь $$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$.

Следовательно, требуется $$$5$$$ секунд, чтобы $$$a$$$ достигло $$$0$$$.