CF1932C LR-remainders

You are given an array $ a $ of length $ n $ , a positive integer $ m $ , and a string of commands of length $ n $ . Each command is either the character 'L' or the character 'R'. Process all $ n $ commands in the order they are written in the string $ s $ . Processing a command is done as follows: - First, output the remainder of the product of all elements of the array $ a $ when divided by $ m $ . - Then, if the command is 'L', remove the leftmost element from the array $ a $ , if the command is 'R', remove the rightmost element from the array $ a $ . Note that after each move, the length of the array $ a $ decreases by $ 1 $ , and after processing all commands, it will be empty. Write a program that will process all commands in the order they are written in the string $ s $ (from left to right).

The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the input. Then descriptions of $ t $ test cases follow. Each test case of the input is given by three lines. The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2\cdot10^5, 1 \le m \le 10^4 $ ) — the initial length of the array $ a $ and the value to take the remainder by. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^4 $ ) — the elements of the array $ a $ . The third line contains a string $ s $ consisting of $ n $ characters 'L' and 'R'. It is guaranteed that the sum of the values of $ n $ for all test cases in a test does not exceed $ 2\cdot10^5 $ .

For each test case, output $ n $ integers $ b_1, b_2, \dots, b_n $ , where $ b_i $ is the remainder when dividing the product of all elements of the current state of the array $ a $ by $ m $ at the beginning of the execution of the $ i $ -th command.

In the first test case of the example: - $ 3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0 $ ; - $ s_1 = \text{L} $ , so we remove the first element and get the array $ [1, 4, 2] $ ; - $ 1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2 $ ; - $ s_2 = \text{R} $ , so we remove the last element and get the array $ [1, 4] $ ; - $ 1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4 $ ; - $ s_3 = \text{R} $ , so we remove the last element and get the array $ [1] $ ; - $ 1 \bmod 6 = 1 $ ; - $ s_4 = \text{L} $ , so we remove the first element and get an empty array.