C. LR-остатки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$ длины $$$n$$$, положительное целое число $$$m$$$ и строка команд из $$$n$$$ символов. Каждая команда — это либо символ 'L', либо символ 'R'.

Обработайте все $$$n$$$ команд в порядке их записи в строке $$$s$$$. Обработка команды производится следующим образом:

  • сначала выведите остаток от произведения значений всех элементов массива $$$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$$$.

Третья строка состоит из $$$n$$$ букв 'L' и 'R' — строка команд $$$s$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$, где $$$b_i$$$ — остаток при делении произведения всех элементов текущего состояния массива $$$a$$$ на $$$m$$$ в начале выполнения $$$i$$$-й команды.

Пример
Входные данные
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
Выходные данные
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}$$$, так что удалим первый элемент и получим пустой массив.