Permutation from Direction String - Repovive Standard Round 2 | Repovive

5C. Permutation from Direction String

1500 pts2s256 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'

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

5C. Permutation from Direction String

Input

Output

Samples

5C. Permutation from Direction String

Constraints

Input

Output

Samples

Constraints