你有 $$$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$$$。每一秒,以下两个动作按顺序发生:
- 当前机器根据其类型更新$$$a$$$。
- 然后,顺时针移动一步到下一台机器。正式地
- 如果您在 $$$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$$$ 整数,表示每个查询的答案。
示例
输入复制
32 2BA3 41 1B206 4BAABBA2 8 32 95
输出复制
23525811
注意
在第一个测试用例中,查询如下:
- 查询 $$$1$$$: $$$a = 3$$$
- 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{3}{2}\right\rfloor = 1$$$。
- 移动到机器$$$2$$$。机器 $$$2$$$ 将 $$$a$$$ 减少 $$$1$$$。现在,$$$a = 1 - 1 = 0$$$。
- 查询 $$$2$$$: $$$a = 4$$$
- 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{4}{2}\right\rfloor = 2$$$。
- 移动到机器$$$2$$$。机器 $$$2$$$ 将 $$$a$$$ 减少 $$$1$$$。现在,$$$a = 2 - 1 = 1$$$。
- 移回机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$。
在第二个测试用例中,只有一个 $$$a = 20$$$ 的查询:
- 从机器 $$$1$$$ 开始。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{20}{2}\right\rfloor = 10$$$。
- 移动到机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{10}{2}\right\rfloor = 5$$$。
- 移动到机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{5}{2}\right\rfloor = 2$$$。
- 移动到机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{2}{2}\right\rfloor = 1$$$。
- 移动到机器$$$1$$$。机器 $$$1$$$ 将 $$$a$$$ 替换为其价值一半的下限。现在,$$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$。
因此,$$$a$$$ 需要 $$$5$$$ 秒才能达到 $$$0$$$。