Blue-Red Permutation solution codeforces

Blue-Red Permutation solution codeforces

You are given an array of integers aa of length nn. The elements of the array can be either different or the same.

Each element of the array is colored either blue or red. There are no unpainted elements in the array. One of the two operations described below can be applied to an array in a single setp:

  • either you can select any blue element and decrease its value by 11;
  • or you can select any red element and increase its value by 11.

Situations in which there are no elements of some color at all are also possible. For example, if the whole array is colored blue or red, one of the operations becomes unavailable.

Blue-Red Permutation solution codeforces

Determine whether it is possible to make 00 or more steps such that the resulting array is a permutation of numbers from 11 to nn?

In other words, check whether there exists a sequence of steps (possibly empty) such that after applying it, the array aa contains in some order all numbers from 11 to nn (inclusive), each exactly once.

Input

The first line contains an integer tt (1t1041≤t≤104) — the number of input data sets in the test.

The description of each set of input data consists of three lines. The first line contains an integer nn (1n21051≤n≤2⋅105) — the length of the original array aa. The second line contains nn integers a1a1a2a2, …, anan (109ai109−109≤ai≤109) — the array elements themselves.

The third line has length nn and consists exclusively of the letters ‘B‘ and/or ‘R‘: iith character is ‘B‘ if aiai is colored blue, and is ‘R‘ if colored red.

Blue-Red Permutation solution codeforces

It is guaranteed that the sum of nn over all input sets does not exceed 21052⋅105.

Output

Print tt lines, each of which contains the answer to the corresponding test case of the input. Print YES as an answer if the corresponding array can be transformed into a permutation, and NO otherwise.

You can print the answer in any case (for example, the strings yEsyesYes, and YES will be recognized as a positive answer).

Example

Blue-Red Permutation solution codeforces

input

Copy
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
output

Copy

Blue-Red Permutation solution codeforces

YES
NO
YES
YES
NO
YES
YES
YES
Note

In the first test case of the example, the following sequence of moves can be performed:

  • choose i=3i=3, element a3=5a3=5 is blue, so we decrease it, we get a=[1,2,4,2]a=[1,2,4,2];
  • choose i=2i=2, element a2=2a2=2 is red, so we increase it, we get a=[1,3,4,2]a=[1,3,4,2];
  • choose i=3i=3, element a3=4a3=4 is blue, so we decrease it, we get a=[1,3,3,2]a=[1,3,3,2];
  • choose i=2i=2, element a2=2a2=2 is red, so we increase it, we get a=[1,4,3,2]a=[1,4,3,2].

We got that aa is a permutation. Hence the answer is YES.

Leave a Comment