B. Strange Machinetime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output You are given $$$n$$$ machines arranged in a circle, where $$$n$$$ is at most $$$20$$$. Each machine is either of type A or type B. The machines are numbered clockwise from $$$1$$$ to $$$n$$$, and the type of the $$$i$$$-th machine is denoted by $$$s_i$$$. Each machine takes an integer $$$x$$$ and updates it according to its type: Type A: Decrease $$$x$$$ by $$$1$$$. Formally, update $$$x := x - 1$$$. Type B: Replace $$$x$$$ with the floor of half its value. Formally, update $$$x := \left\lfloor\frac{x}{2}\right\rfloor$$$, where $$$\lfloor y\rfloor$$$ denotes the floor of $$$y$$$, which is the greatest integer less than or equal to $$$y$$$. You are given $$$q$$$ queries, each consisting of a single integer $$$a$$$. In each query, you start at machine $$$1$$$ holding an integer $$$a$$$. Each second, the following two actions occur in order: The current machine updates $$$a$$$ according to its type. Then, move one step clockwise to the next machine. Formally If you are at machine $$$i$$$ where $$$1 \le i \le n - 1$$$, move to machine $$$i + 1$$$. If you are at machine $$$n$$$, move to machine $$$1$$$. This process continues until your integer $$$a$$$ becomes $$$0$$$. For each query, determine the number of seconds required for $$$a$$$ to reach $$$0$$$.Note that all queries are independent of each other.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n\le 20$$$, $$$1\le q\le 10^4$$$) — the number of machines, and the number of queries, respectively.The second line of each test case contains a string $$$s$$$ ($$$|s| = n$$$ and $$$s_i = \mathtt{A} \text{ or }\mathtt{B}$$$) — the types of the machines.The third line of each test case contains $$$q$$$ integers $$$a_1, a_2, \ldots, a_q$$$ ($$$1\le a_i\le 10^9$$$) — the initial integer of each query.Note that there are no constraints on the sum of $$$n$$$ over all test cases. It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^4$$$. OutputFor each test case, output $$$q$$$ integers representing the answers to each query.ExampleInput32 2BA3 41 1B206 4BAABBA2 8 32 95Output23525811NoteIn the first test case, the queries are as follows: Query $$$1$$$: $$$a = 3$$$ Start at machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{3}{2}\right\rfloor = 1$$$. Move to machine $$$2$$$. Machine $$$2$$$ decreases $$$a$$$ by $$$1$$$. Now, $$$a = 1 - 1 = 0$$$. Therefore, it takes $$$2$$$ seconds for $$$a$$$ to reach $$$0$$$. Query $$$2$$$: $$$a = 4$$$ Start at machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{4}{2}\right\rfloor = 2$$$. Move to machine $$$2$$$. Machine $$$2$$$ decreases $$$a$$$ by $$$1$$$. Now, $$$a = 2 - 1 = 1$$$. Move back to machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$. Therefore, it takes $$$3$$$ seconds for $$$a$$$ to reach $$$0$$$. In the second test case, there is only one query with $$$a = 20$$$: Start at machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{20}{2}\right\rfloor = 10$$$. Move to machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{10}{2}\right\rfloor = 5$$$. Move to machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{5}{2}\right\rfloor = 2$$$. Move to machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{2}{2}\right\rfloor = 1$$$. Move to machine $$$1$$$. Machine $$$1$$$ replaces $$$a$$$ with the floor of half its value. Now, $$$a = \left\lfloor\frac{1}{2}\right\rfloor = 0$$$. Therefore, it takes $$$5$$$ seconds for $$$a$$$ to reach $$$0$$$.