CF2150A Incremental Path

[Rymdkraft - Rymdsylt](https://soundcloud.com/rymdkraft/rymdsylt) ⠀ Hacks are disabled in this problem. There is a strip containing $ 10^9 $ cells, numbered from $ 1 $ to $ 10^9 $ . Each cell is either black or white. Initially, $ m $ distinct cells $ a_1, a_2, \ldots, a_m $ are black, and the others are white. If a person is on some cell $ x $ , he might be given two types of commands: - $ \texttt{A} $ : jump to the next cell, i.e. cell $ x + 1 $ ; - $ \texttt{B} $ : jump to the next white cell, i.e. the minimum $ y > x $ such that cell $ y $ is white. There is a string $ s $ of length $ n $ , consisting of $ n $ commands. For each $ i $ from $ 1 $ to $ n $ in order, a person - starts from cell $ 1 $ ; - executes the first $ i $ commands in the string; - colors the last visited cell black (if it was already black, it remains black). You wonder which cells are black at the end of the process. Print them in increasing order.

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 $ m $ ( $ 1 \leq n \leq 10^5 $ , $ 1 \leq m \leq 10^5 $ ) — the number of commands and the number of black cells at the beginning. The second line of each test case contains a string $ s $ of length $ n $ , consisting of characters $ \texttt{A} $ and $ \texttt{B} $ , representing the commands. The third line of each test case contains $ m $ integers $ a_1, a_2, \ldots, a_m $ ( $ 1 \leq a_1 < a_2 < \ldots < a_m \leq 10^9 $ ) — the initial black cells. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ , and the sum of $ m $ over all test cases does not exceed $ 10^5 $ .

For each test case, print two lines: - in the first line, print a single integer $ k $ : the number of black cells at the end; - in the second line, print the labels of the black cells, in increasing order.

In the first test case, initially the only black cells are $ 2 $ and $ 5 $ . Person $ 1 $ : - starts from cell $ 1 $ ; - executes command $ \texttt{B} $ , going to the next white cell ( $ 3 $ ); - colors cell $ 3 $ black. Person $ 2 $ : - starts from cell $ 1 $ ; - executes command $ \texttt{B} $ , going to the next white cell ( $ 4 $ ); - executes command $ \texttt{A} $ , going to the next cell ( $ 5 $ ); - colors cell $ 5 $ black (it was already black, so it remains black). Person $ 3 $ : - starts from cell $ 1 $ ; - executes command $ \texttt{B} $ , going to the next white cell ( $ 4 $ ); - executes command $ \texttt{A} $ , going to the next cell ( $ 5 $ ); - executes command $ \texttt{B} $ , going to the next white cell ( $ 6 $ ); - colors cell $ 6 $ black. At the end, the black cells are $ \{2, 3, 5, 6\} $ . In the second test case, the three people end up in cells $ 2 $ , $ 3 $ , and $ 6 $ , respectively.