QED's Favorite Permutation
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 1700
Tags: data structures, implementation, sortings

QED is given a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$. He also has a string $$$s$$$ of length $$$n$$$ containing only characters $$$\texttt{L}$$$ and $$$\texttt{R}$$$. QED only likes permutations that are sorted in non-decreasing order. To sort $$$p$$$, he can select any of the following operations and perform them any number of times:

- Choose an index $$$i$$$ such that $$$s_i = \texttt{L}$$$. Then, swap $$$p_i$$$ and $$$p_{i-1}$$$. It is guaranteed that $$$s_1 \neq \texttt{L}$$$.
- Choose an index $$$i$$$ such that $$$s_i = \texttt{R}$$$. Then, swap $$$p_i$$$ and $$$p_{i+1}$$$. It is guaranteed that $$$s_n \neq \texttt{R}$$$.

He is also given $$$q$$$ queries. In each query, he selects an index $$$i$$$ and changes $$$s_i$$$ from $$$\texttt{L}$$$ to $$$\texttt{R}$$$ (or from $$$\texttt{R}$$$ to $$$\texttt{L}$$$). Note that the changes are persistent.

After each query, he asks you if it is possible to sort $$$p$$$ in non-decreasing order by performing the aforementioned operations any number of times. Note that before answering each query, the permutation $$$p$$$ is reset to its original form.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) – the length of the permutation and the number of queries.

The following line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$, $$$p$$$ is a permutation).

The following line contains $$$n$$$ characters $$$s_1s_2 \ldots s_n$$$. It is guaranteed that $$$s_i$$$ is either $$$\texttt{L}$$$ or $$$\texttt{R}$$$, $$$s_1 = \texttt{R}$$$, and $$$s_n = \texttt{L}$$$.

The following $$$q$$$ lines contain an integer $$$i$$$ ($$$2 \leq i \leq n-1$$$), denoting that $$$s_i$$$ is changed from $$$\texttt{L}$$$ to $$$\texttt{R}$$$ (or from $$$\texttt{R}$$$ to $$$\texttt{L}$$$).

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, $$$s = \texttt{RRRLL}$$$ after the first query. QED may sort $$$p$$$ using the following operations:

- Initially, $$$p = [1,4,2,5,3]$$$.
- Select $$$i = 2$$$ and swap $$$p_2$$$ with $$$p_{3}$$$. Now, $$$p = [1,2,4,5,3]$$$.
- Select $$$i = 5$$$ and swap $$$p_5$$$ with $$$p_{4}$$$. Now, $$$p = [1,2,4,3,5]$$$.
- Select $$$i = 4$$$ and swap $$$p_4$$$ with $$$p_{3}$$$. Now, $$$p = [1,2,3,4,5]$$$, which is in non-decreasing order.

It can be shown that it is impossible to sort the array after all three updates of the first testcase.

Example input:
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

Example output:
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES

Editorial: