D. Любимая перестановка ЧТД
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

ЧТД подарили перестановку$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. У него также есть строка $$$s$$$ длины $$$n$$$, содержащая только символы $$$\texttt{L}$$$ и $$$\texttt{R}$$$. ЧТД любит только те перестановки, которые отсортированы в неубывающем порядке. Чтобы отсортировать $$$p$$$, он может выбирать любые из следующих операций и выполнять их любое количество раз:

  • Выбрать индекс $$$i$$$ такой, что $$$s_i = \texttt{L}$$$. Затем поменять местами $$$p_i$$$ и $$$p_{i-1}$$$. Гарантируется, что $$$s_1 \neq \texttt{L}$$$.
  • Выбрать индекс $$$i$$$ такой, что $$$s_i = \texttt{R}$$$. Затем поменять местами $$$p_i$$$ и $$$p_{i+1}$$$. Гарантируется, что $$$s_n \neq \texttt{R}$$$.

Ему также дается $$$q$$$ запросов. В каждом запросе он выбирает индекс $$$i$$$ и меняет $$$s_i$$$ с $$$\texttt{L}$$$ на $$$\texttt{R}$$$ (или с $$$\texttt{R}$$$ на $$$\texttt{L}$$$). Обратите внимание, что изменения постоянны.

После каждого запроса он спрашивает вас, можно ли отсортировать $$$p$$$ в неубывающем порядке, выполнив вышеупомянутые операции любое количество раз. Обратите внимание, что перед каждым запросом перестановка $$$p$$$ сбрасывается к своему исходному значению.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, расположенных в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ — не перестановка ($$$2$$$ дважды встречается в массиве), и $$$[1,3,4]$$$ — тоже не перестановка ($$$n=3$$$, но в массиве есть $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — длина перестановки и количество запросов.

Следующая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$, $$$p$$$ — перестановка).

Следующая строка содержит $$$n$$$ символов $$$s_1s_2 \ldots s_n$$$. Гарантируется, что $$$s_i$$$ — это либо $$$\texttt{L}$$$, либо $$$\texttt{R}$$$, $$$s_1 = \texttt{R}$$$, а $$$s_n = \texttt{L}$$$.

Следующие $$$q$$$ строк содержат по одному целому числу $$$i$$$ ($$$2 \leq i \leq n-1$$$), обозначающему, что $$$s_i$$$ изменено с $$$\texttt{L}$$$ на $$$\texttt{R}$$$ (или с $$$\texttt{R}$$$ на $$$\texttt{L}$$$). Запросы изменяют строку, то есть следующее изменение будет применяться к обновлённой строке.

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

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

Для каждого запроса выведите «YES» (без кавычек), если возможно отсортировать перестановку, или «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
5 3
1 4 2 5 3
RLRLL
2
4
3
8 5
1 5 2 4 8 3 6 7
RRLLRRRL
4
3
5
3
4
6 2
1 2 3 4 5 6
RLRLRL
4
5
Выходные данные
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
Примечание

В первом наборе входных данных $$$s = \texttt{RRRLL}$$$ после первого запроса. ЧТД может отсортировать $$$p$$$ с помощью следующих операций:

  • Изначально, $$$p = [1,4,2,5,3]$$$.
  • Выбрать $$$i = 2$$$ и поменять местами $$$p_2$$$ и $$$p_{3}$$$. Теперь $$$p = [1,2,4,5,3]$$$.
  • Выбрать $$$i = 5$$$ и поменять местами $$$p_5$$$ и $$$p_{4}$$$. Теперь $$$p = [1,2,4,3,5]$$$.
  • Выбрать $$$i = 4$$$ и поменять местами $$$p_4$$$ и $$$p_{3}$$$. Теперь $$$p = [1,2,3,4,5]$$$, то есть перестановка отсортирована в неубывающем порядке.

Можно показать, что невозможно отсортировать массив после выполнения трёх обновлений первого набора входных данных.