1932C.md (2601B)
1 Source: https://codeforces.com/problemset/problem/1932/C 2 3 C. LR-remainders 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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'. 22 23 Process all $n$ commands in the order they are written in the string $s$. Processing a command is done as follows: 24 25 * First, output the remainder of the product of all elements of the array $a$ when divided by $m$. 26 * 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$. 27 28 Note that after each move, the length of the array $a$ decreases by $1$, and after processing all commands, it will be empty. 29 30 Write a program that will process all commands in the order they are written in the string $s$ (from left to right). 31 32 Input 33 34 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. 35 36 Each test case of the input is given by three lines. 37 38 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. 39 40 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$. 41 42 The third line contains a string $s$ consisting of $n$ characters 'L' and 'R'. 43 44 It is guaranteed that the sum of the values of $n$ for all test cases in a test does not exceed $2\cdot10^5$. 45 46 Output 47 48 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. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 4 6 58 59 3 1 4 2 60 61 LRRL 62 63 5 1 64 65 1 1 1 1 1 66 67 LLLLL 68 69 6 8 70 71 1 2 3 4 5 6 72 73 RLLLRR 74 75 1 10000 76 77 10000 78 79 R 80 ``` 81 82 Output 83 84 ``` 85 0 2 4 1 86 0 0 0 0 0 87 0 0 0 4 4 4 88 0 89 ``` 90 91 Note 92 93 In the first test case of the example: 94 95 * $3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$; 96 * $s_1 = \text{L}$, so we remove the first element and get the array $[1, 4, 2]$; 97 * $1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$; 98 * $s_2 = \text{R}$, so we remove the last element and get the array $[1, 4]$; 99 * $1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$; 100 * $s_3 = \text{R}$, so we remove the last element and get the array $[1]$; 101 * $1 \bmod 6 = 1$; 102 * $s_4 = \text{L}$, so we remove the first element and get an empty array.