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

$ curl repovive.com/contests/19/problems/F

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

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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

19F. Costly Substrings

Constraints

Input

Output

Samples

19F. Costly Substrings

Constraints

Input

Output

Samples