F. Land Trade
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Recently, Bobo had an idea to buy a piece of land from a landholder. Bobo, however, doesn't want to buy the entire rectangular land. Instead, he only wants to buy a part of the land which satisfies certain requirements.

Mathematically speaking, the rectangular land is defined by the set of points $$$$$$ L = \{(x, y): x_{\min} \leq x \leq x_{\max}, y_{\min} \leq y \leq y_{max} \} $$$$$$ in Cartesian coordinates. Bobo's requirements are encoded into a logic formula. The logic formula is described in the following syntax: 


<formula> := "(" <formula> "&" <formula> ")"
           | "(" <formula> "|" <formula> ")"
           | "(" <formula> "^" <formula> ")"
           | "(" "!" <formula> ")"
           | <atomic-formula>
<atomic-formula> := "[" <decimal> "," <decimal> "," <decimal> "]"
where "&", "|", and "^" are And, Inclusive Or, and Exclusive Or operators, respectively; <decimal> refers to any signed decimal integer; an atomic formula $$$[a, b, c]$$$ denotes a constraint $$$ax + by + c \geq 0$$$. Formally, the part of the land he wants is the set of points in $$$L$$$ satisfying the given logical formula.

To proceed with the transaction, they want to know the area of the part of the land Bobo wants to buy. Can you tell them the answer?

Input

The first line of the input contains four integers $$$x_{\min}, x_{\max}, y_{\min}, y_{\max}$$$ $$$(x_{\min} \lt x_{\max}, y_{\min} \lt y_{\max})$$$, the absolute values of which do not exceed $$$1\,000$$$, specifying the region of the rectangular land.

The second line of the input is the logic formula. The formula contains no more than $$$10\,000$$$ characters and, at most $$$300$$$ atomic formulas. The logic formula strictly conforms to the syntax of the problem statement; there is neither space between tokens nor any omission of parentheses. For every atomic formula $$$[a, b, c]$$$, it is guaranteed that $$$|a|, |b|, |c| \leq 1\,000$$$ and $$$a^2+b^2 \neq 0$$$.

Output

Output a number in a line, denoting the area of the part of the land the landlord wants to buy. The answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
0 1 0 1
([-1,1,0]^[-1,-1,1])
Output
0.5
Input
-5 10 -10 5
((!([1,2,-3]&[10,3,-2]))\\
^([-2,3,1]|[5,-2,7]))
Output
70.4516934046
Input
0 1 -1 1
([1,1,1]&[-1,-1,-1])
Output
0
Note

Note that in the second sample test, there exists "$$$\backslash\backslash$$$" that represents a line break, which is not present in the real input. Here, we add the line break only for better formatting and illustration.

The plots for the first two sample test data are shown below, where the filled part represents the part of the land Bobo wants to buy.