CF2156B Strange Machine

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](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) 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: 1. The current machine updates $ a $ according to its type. 2. 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.

Each 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 $ .

For each test case, output $ q $ integers representing the answers to each query.

In the first test case, the queries are as follows: - Query $ 1 $ : $ a = 3 $ 1. 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 $ . 2. 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 $ 1. 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 $ . 2. Move to machine $ 2 $ . Machine $ 2 $ decreases $ a $ by $ 1 $ . Now, $ a = 2 - 1 = 1 $ . 3. 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 $ : 1. 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 $ . 2. 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 $ . 3. 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 $ . 4. 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 $ . 5. 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 $ .