#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/C

Repovive

Permutation from Direction String - Repovive Standard Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

5C. Permutation from Direction String

1500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

Consider any permutation $p_1, p_2, \dots, p_n$ of the integers $1, 2, \dots, n$ .
Define $p_0 = n+1$ and $p_{n+1} = n+2$ .

For each index $i$ ( $1 \le i \le n$ ) we compute a character $c_i$ as follows:

Let $x$ be the index of the nearest greater element to the left of $i$ : $x = \max\{j \mid 0 \le j < i \text{ and } p_j > p_i\}$ .
Let $y$ be the index of the nearest greater element to the right of $i$ : $y = \min\{j \mid i < j \le n+1 \text{ and } p_j > p_i\}$ .
If $p_x < p_y$ then $c_i =$ L, otherwise $c_i$ = R.

In other words, we look at the closest larger element on the left and the closest larger element on the right. The character L means the left one is smaller, R means the right one is smaller.

Now you are given the string $s$ . Determine whether there exists a permutation $p$ such that $c_i = s_i$ for every $i = 1 \dots n$ .

If no such permutation exists, print No.
If it exists, print Yes and on the next line output any permutation $p$ that satisfies the condition.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ s \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{Yes / No} \\ p_1 \quad p_2 \quad \dots \quad p_n \quad \text{(if answer is Yes)} \end{array} \right\} \times t

Samples

Input

Case 1

3
RLL

Case 2

3
LRR

Case 3

1
L

Case 4

2
RL

Case 5

4
RRRL

Explanation

Case 1

$i=1$ : left greater $= p_0=4$ , right greater $= p_2=3$ . Since $4>3$ , the direction is 'R'
$i=2$ : left greater $= p_0=4$ , right greater $= p_4=5$ . Since $4<5$ , the direction is 'L'
$i=3$ : left greater $= p_2=3$ , right greater $= p_4=5$ . Since $3<5$ , the direction is 'L'

Case 2

Impossible

Case 3

$i=1$ : left greater $= p_0=2$ , right greater $= p_2=3$ . Since $2<3$ , the direction is 'L'

Case 4

$i=1$ : left greater $= p_0=3$ , right greater $= p_2=2$ . Since $3>2$ , the direction is 'R'
$i=2$ : left greater $= p_0=3$ , right greater $= p_3=4$ . Since $3<4$ , the direction is 'L'

Case 5

$i=1$ : left greater $= p_0=5$ , right greater $= p_2=2$ . Since $5>2$ , the direction is 'R'
$i=2$ : left greater $= p_0=5$ , right greater $= p_3=3$ . Since $5>3$ , the direction is 'R'
$i=3$ : left greater $= p_0=5$ , right greater $= p_4=4$ . Since $5>4$ , the direction is 'R'
$i=4$ : left greater $= p_0=5$ , right greater $= p_5=6$ . Since $5<6$ , the direction is 'L'

Output

Case 1

Yes
2 3 1

Case 2

No

Case 3

Yes
1

Case 4

Yes
1 2

Case 5

Yes
1 2 3 4

Consider any permutation $p_1, p_2, \dots, p_n$ of the integers $1, 2, \dots, n$ .
Define $p_0 = n+1$ and $p_{n+1} = n+2$ .

For each index $i$ ( $1 \le i \le n$ ) we compute a character $c_i$ as follows:

Let $x$ be the index of the nearest greater element to the left of $i$ : $x = \max\{j \mid 0 \le j < i \text{ and } p_j > p_i\}$ .
Let $y$ be the index of the nearest greater element to the right of $i$ : $y = \min\{j \mid i < j \le n+1 \text{ and } p_j > p_i\}$ .
If $p_x < p_y$ then $c_i =$ L, otherwise $c_i$ = R.

In other words, we look at the closest larger element on the left and the closest larger element on the right. The character L means the left one is smaller, R means the right one is smaller.

Now you are given the string $s$ . Determine whether there exists a permutation $p$ such that $c_i = s_i$ for every $i = 1 \dots n$ .

If no such permutation exists, print No.
If it exists, print Yes and on the next line output any permutation $p$ that satisfies the condition.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ s \end{array} \right\} \times t

\left. \begin{array}{l} \text{Yes / No} \\ p_1 \quad p_2 \quad \dots \quad p_n \quad \text{(if answer is Yes)} \end{array} \right\} \times t

$i=1$ : left greater $= p_0=4$ , right greater $= p_2=3$ . Since $4>3$ , the direction is 'R'
$i=2$ : left greater $= p_0=4$ , right greater $= p_4=5$ . Since $4<5$ , the direction is 'L'
$i=3$ : left greater $= p_2=3$ , right greater $= p_4=5$ . Since $3<5$ , the direction is 'L'

$i=1$ : left greater $= p_0=2$ , right greater $= p_2=3$ . Since $2<3$ , the direction is 'L'

$i=1$ : left greater $= p_0=3$ , right greater $= p_2=2$ . Since $3>2$ , the direction is 'R'
$i=2$ : left greater $= p_0=3$ , right greater $= p_3=4$ . Since $3<4$ , the direction is 'L'

$i=1$ : left greater $= p_0=5$ , right greater $= p_2=2$ . Since $5>2$ , the direction is 'R'
$i=2$ : left greater $= p_0=5$ , right greater $= p_3=3$ . Since $5>3$ , the direction is 'R'
$i=3$ : left greater $= p_0=5$ , right greater $= p_4=4$ . Since $5>4$ , the direction is 'R'
$i=4$ : left greater $= p_0=5$ , right greater $= p_5=6$ . Since $5<6$ , the direction is 'L'