There are two graphs $A$ and $B$ with the same set of edges. Each vertex is colored either red or black and has an associated weight $a_i$.

You may perform the following operation zero or more times:

1. Choose one graph and two adjacent vertices $u, v$.
2. Swap $a_u$ and $a_v$.
3. If $u$ and $v$ have the same color, flip the colors of both vertices; otherwise, their colors remain unchanged.

Determine whether the two graphs can become identical, meaning that all vertices have the same color and the same weight.

Input

The input contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains two integers $n$ and $m$, representing the number of vertices and edges.

The next $m$ lines each contain two integers $u, v$, representing an edge.

The next line contains $n$ integers, where the $i$-th integer $a_i$ is the weight of the $i$-th vertex in graph $A$.

The next line contains a string of length $n$, where the $i$-th character $c_i$ is the color of the $i$-th vertex in graph $A$, either R or B.

The next line contains $n$ integers, where the $i$-th integer $b_i$ is the weight of the $i$-th vertex in graph $B$.

The next line contains a string of length $n$, where the $i$-th character $d_i$ is the color of the $i$-th vertex in graph $B$, either R or B.

Output

For each test case, output a single line: YES if the two graphs can become identical, and NO otherwise.

Examples

Input 1

3
2 1
1 2
3 4
RR
4 3
BB
3 2
1 2
2 3
1 1 1
RBR
1 1 1
BBB
3 3
1 2
2 3
3 1
1 1 1
RBR
1 1 1
BBB

Output 1

YES
NO
YES

Constraints

For all test cases, it is guaranteed that $1 \leq T \leq 3 \times 10^4$, $1 \leq n, \sum n \leq 10^6$, $0 \leq m, \sum m \leq 10^6$, $1 \leq u, v \leq n$, $0 \leq a_i, b_i \leq 10^9$, $c_i, d_i \in \{'R', 'B'\}$, and the graphs contain no multiple edges or self-loops.