Problem Description

As we all know, electrical resistance connections include series and parallel connections. The total resistance of a circuit can be considered as the equivalent resistance $R_{ekv}$ of that circuit. When resistances are connected in series, it can be represented as:

$$\text{(R1-R2-R3-...-RK)}$$

And the formula is satisfied:

$$R_{ekv}=\sum_{i=1}^K R_i$$

When connected in parallel, it can be represented as:

$$\text{(R1|R2|R3|...|RK)}$$

And the formula is satisfied:

$$R_{ekv}=\frac{1}{\sum_{i=1}^K \frac{1}{R_i}}$$

Given $N$ types of resistors with resistance values $R_i$ and sufficient wires, and a specified connection method for these resistors, calculate the equivalent resistance value of the entire circuit.

Input Format

The first line contains an integer $N$.

The second line contains $N$ real numbers $R_i$.

The third line contains a string $S$ representing the circuit. The string only contains $\texttt R$, $\texttt 1 \sim \texttt 9$, $\texttt ($ , $\texttt )$ , $\texttt -$, and $\texttt |$. The data guarantees that there will be no mismatched or illegal parentheses, and the number of parentheses will be minimized. No pair of parentheses will contain both $\texttt -$ and $\texttt |$ simultaneously. The circuit only includes the given $N$ types of resistors and may appear any number of times (including zero).

Output Format

Output the equivalent resistance value of the entire circuit. The output is considered correct if it differs from the standard answer by no more than $10^{-5}$.

Sample Input and Output

Sample Input #1

3
2 3 6
(R1-R2-R3)

Sample Output #1

11.00000

Sample Input #2

3
2 3 6
(R1|R2|R3)

Sample Output #2

1.00000

Sample Input #3

5
5.0 5.0 5.0 5.0 5.0
((R1-(R2|R3)-(R4|R5))|(R1-(R2|R3)-(R4|R5)))

Sample Output #3

5.00000

Notes

[Data Range and Constraints]

• For $20\%$ of the data, $N=3$ and the circuit exactly includes these three resistors.
• For $40\%$ of the data, $S$ only contains one pair of parentheses.
• For $100\%$ of the data, $1 \le N \le 9$, $0 < R_i < 100$, $1 \le |S| \le 10^5$.

[Translation and Original Problem]

This problem is translated from COCI 2015-2016 #7 Task 4 Otpor.

The score for this problem is set according to the original COCI problem, with a maximum score of $120$.

见题面 Input 部分

见题面 Output 部分