D. QED's Favorite Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

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

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).

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
Output
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
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.