Costly Substrings - Repovive Starter Round 6 | Repovive

19F. Costly Substrings

3000 pts2s256 MB

You are given a string $s$ consisting only of the characters L and R.

Consider any non-empty substring of $s$ . You must delete all of its characters using the following operation:

Delete either the leftmost or the rightmost character of the current substring.
Deleting the leftmost character is free if it is L; if it is R, it costs $c_R$ .
Deleting the rightmost character is free if it is R; if it is L, it costs $c_L$ .

Each substring is processed independently, starting from its original contents.

For every non-empty substring of $s$ , consider the minimum total cost needed to delete it completely. Find the sum of these minimum costs over all non-empty substrings of $s$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le c_L, c_R \le 10^4$
$s$ consists only of the characters L and R
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t

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

Output

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

Samples

Input

Case 1

1 5 3
L

Case 2

2 5 3
RL

Case 3

3 2 4
RLL

Case 4

4 5 3
RLLR

Explanation

Case 1

The only substring is $\texttt{L}$ , and it can be deleted from the left for free.

Case 2

The one-character substrings cost $0$ . For $\texttt{RL}$ , deleting the leftmost character costs $3$ , after which the remaining character can be deleted for free. Thus the total is $3$ .

Case 3

The substrings $\texttt{R}$ , $\texttt{L}$ , $\texttt{L}$ , and $\texttt{LL}$ cost $0$ . The minimum costs for $\texttt{RL}$ and $\texttt{RLL}$ are $2$ and $4$ , respectively, so their sum is $6$ .

Case 4

The only substrings with positive minimum cost are $\texttt{RL}$ , $\texttt{RLL}$ , and $\texttt{RLLR}$ . Each of them costs $3$ , giving a total of $9$ .

Output

Case 1

Case 2

Case 3

Case 4

Input

Case 1

5 4 6
RRLLR

Case 2

6 1 10
RLRLLR

Explanation

Case 1

The one-character substrings and the substrings consisting only of equal characters cost $0$ . The positive minimum costs of the remaining substrings add up to $36$ .

Case 2

Processing every substring independently and adding its minimum deletion cost gives $20$ .

Output

Case 1

Case 2

You are given a string $s$ consisting only of the characters L and R.

Consider any non-empty substring of $s$ . You must delete all of its characters using the following operation:

Delete either the leftmost or the rightmost character of the current substring.
Deleting the leftmost character is free if it is L; if it is R, it costs $c_R$ .
Deleting the rightmost character is free if it is R; if it is L, it costs $c_L$ .

Each substring is processed independently, starting from its original contents.

For every non-empty substring of $s$ , consider the minimum total cost needed to delete it completely. Find the sum of these minimum costs over all non-empty substrings of $s$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le c_L, c_R \le 10^4$
$s$ consists only of the characters L and R
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t

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

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

The only substring is $\texttt{L}$ , and it can be deleted from the left for free.

The one-character substrings cost $0$ . For $\texttt{RL}$ , deleting the leftmost character costs $3$ , after which the remaining character can be deleted for free. Thus the total is $3$ .

The substrings $\texttt{R}$ , $\texttt{L}$ , $\texttt{L}$ , and $\texttt{LL}$ cost $0$ . The minimum costs for $\texttt{RL}$ and $\texttt{RLL}$ are $2$ and $4$ , respectively, so their sum is $6$ .

The only substrings with positive minimum cost are $\texttt{RL}$ , $\texttt{RLL}$ , and $\texttt{RLLR}$ . Each of them costs $3$ , giving a total of $9$ .

The one-character substrings and the substrings consisting only of equal characters cost $0$ . The positive minimum costs of the remaining substrings add up to $36$ .

Processing every substring independently and adding its minimum deletion cost gives $20$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19F. Costly Substrings

Constraints

Input

Output

Samples

19F. Costly Substrings

Constraints

Input

Output

Samples