← 返回题目列表

Codeforces · 1932/C

C. LR-余数

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$、一个正整数 $$$m$$$ 和一个长度为 $$$n$$$ 的命令字符串。每个命令要么是字符“L”,要么是字符“R”。

按照字符串 $$$s$$$ 中写入的顺序处理所有 $$$n$$$ 命令。处理命令的过程如下:

- 首先,输出数组 $$$a$$$ 所有元素的乘积除以 $$$m$$$ 的余数。
- 然后,如果命令是“L”,则从数组$$$a$$$中删除最左边的元素,如果命令是“R”,则从数组$$$a$$$中删除最右边的元素。

注意,每次移动后,数组$$$a$$$的长度会减少$$$1$$$,处理完所有命令后,它将为空。

编写一个程序,按照字符串 $$$s$$$ 中写入的顺序(从左到右)处理所有命令。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例的描述。

输入的每个测试用例由三行给出。

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$$$) — 数组 $$$a$$$ 的初始长度和取余数的值。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — 数组 $$$a$$$ 的元素。

第三行包含一个字符串 $$$s$$$,由 $$$n$$$ 字符“L”和“R”组成。

保证一次测试中所有测试用例的$$$n$$$值之和不超过$$$2\cdot10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$,其中 $$$b_i$$$ 是在执行第 $$$i$$$ 命令开始时将数组 $$$a$$$ 当前状态的所有元素的乘积除以 $$$m$$$ 的余数。

示例

输入 #1

4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

输出 #1

0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0

注意

在示例的第一个测试用例中:

- $$$3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$$$;
- $$$s_1 = \text{L}$$$,所以我们删除第一个元素并得到数组 $$$[1, 4, 2]$$$;
- $$$1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$$$;
- $$$s_2 = \text{R}$$$,所以我们删除最后一个元素并得到数组$$$[1, 4]$$$;
- $$$1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$$$;
- $$$s_3 = \text{R}$$$,所以我们删除最后一个元素并得到数组$$$[1]$$$;
- $$$1 \bmod 6 = 1$$$;
- $$$s_4 = \text{L}$$$,因此我们删除第一个元素并得到一个空数组。