题目描述

有 $n$ 台按顺时针排列的机器，$n\le 20$。每台机器的类型为 A 或 B。机器按顺时针编号为 $1\dots n$，第 $i$ 台机器的类型记作 $s_i$。机器对当前持有的整数 $x$ 做如下更新：

• 类型 A：将 $x$ 减 $1$，即 $x:=x-1$；
• 类型 B：将 $x$ 置为其二分之一向下取整，即 $x:=\lfloor x/2\rfloor$。

你有 $q$ 个查询，每个查询给出一个整数 $a$。对于单个查询，从机器 $1$ 出发，初始持有整数 $a$。每秒钟按顺序执行以下两步：

1. 当前机器根据其类型更新 $a$；
2. 顺时针移动到下一个机器（若当前在第 $i$ 台，$1\le i\le n-1$ 则移动到 $i+1$，若在第 $n$ 台则移动到 $1$）。

当且仅当 $a$ 变为 $0$ 时停止。对于每个查询，求 $a$ 变为 $0$ 所需的秒数。

注意：不同查询之间互不影响（每次从初始状态开始独立模拟）。

输入格式

输入包含若干测试用例：

• 第 $1$ 行：整数 $t$，表示测试用例个数。（$1\le t\le 10^4$）

• 随后对每个测试用例，包含 $3$ 行：

  1. 第 $1$ 行：两个整数 $n$ 和 $q$（$1\le n\le 20$，$1\le q\le 10^4$） —— 机器数量与查询数量。
  2. 第 $2$ 行：长度为 $n$ 的字符串 $s$，每个字符为 A 或 B，表示各台机器的类型（$|s|=n$，第 $i$ 个字符为 $s_i$）。
  3. 第 $3$ 行：$q$ 个整数 $a_1,a_2,\dots,a_q$，表示每个查询的初始整数（$1\le a_i\le 10^9$）。

• 所有测试用例中 $q$ 的总和不超过 $10^4$。对 $n$ 的总和没有特殊限制。

输出格式

对每个测试用例输出 一行，该行包含 $q$ 个整数（用空格分隔），分别为对应 $q$ 个查询的答案：每个初始值 $a_i$ 变为 $0$ 所需的秒数。

样例输入

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$（机器序列 B,A）：

  • 在机器 $1$（B）上：$a\leftarrow\lfloor 3/2\rfloor=1$；
  • 移到机器 $2$（A）：$a\leftarrow 1-1=0$。共 $2$ 秒。

• 样例 $1$ 中，第二个查询 $a=4$：

  • 机器 $1$（B）：$4\to2$；
  • 机器 $2$（A）：$2\to1$；
  • 机器 $1$（B）：$1\to0$，共 $3$ 秒。

• 样例 2（只有一台 B 机，$a=20$）：每秒 $a\to\lfloor a/2\rfloor$，需要 $5$ 次直到 $0$。