It is late at night and you found a logical expression on the blackboard, which you believe is the secret to figure out if your gang is going to be attacked tomorrow.
Your immediate reaction is to copy the expression and take it to the big bosses. Luckily, you remembered that mafia bosses don't enjoy surprises, and they want your expression to be simple and clean.
Given the logical expression in the board, having variables represented by english letters A-Z, and the operators OR and AND, simplify it using Morgan's law, that is:
To help you, we will use the following format:
This is also valid for three or more variables. The expression will have variables, represented by letters A-Z: if it is a lower case letter, it is a negated variable. It may also have parenthesis that group expressions, so you must solve the expressions between the parenthesis first. There may also be square brackets, in which case you must apply the rules above.
Don't simplify the expression beyond applying the rules described in the problem.
The input is a logical expression having at most 200 characters. Each character can be a variable (A-Z), a negated variable (a-z), the operator OR (+) or the operator AND (*). Also, it can have parenthesis. A negation is represented by a lowercase character or a logic block between square brackets ([ ]).
Print the simplified logic expression.
## Input
The input is a logical expression having at most 200 characters. Each character can be a variable (A-Z), a negated variable (a-z), the operator OR (+) or the operator AND (*). Also, it can have parenthesis. A negation is represented by a lowercase character or a logic block between square brackets ([ ]).
## Output
Print the simplified logic expression.
[samples]
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ with $ 1 \leq n, q \leq 100{,}000 $.
Let $ s \in \{ \texttt{L}, \texttt{R} \}^{n+1} $ be a string representing signs on a road of length $ n $, where each character is either 'L' (start) or 'R' (end).
Let $ P \subseteq \{1, \dots, n+1\}^2 $ be the set of matched pairs $ (i, j) $ with $ i < j $, $ s[i] = \texttt{L} $, $ s[j] = \texttt{R} $, and the pairs form a valid nesting (i.e., the string is a valid parentheses-like sequence).
For any interval $ [a, b] \subseteq [1, n+1] $ with $ 1 \leq a < b \leq n+1 $, define the **active start sign** at position $ i \in [a, b) $ as the most recent unmatched 'L' at index $ \leq i $.
The **speed limit** between sign $ i $ and $ i+1 $ is determined by the active start sign at $ i $.
**Constraints**
1. $ s $ contains exactly $ k $ 'L's and $ k $ 'R's for some $ k \in \mathbb{Z}^+ $, and forms a valid nested structure.
2. For each query, given $ a, b \in \mathbb{Z} $ with $ 1 \leq a < b \leq n+1 $, we consider the subinterval $ [a, b] $.
**Objective**
For each query $ (a, b) $, find the **minimum number of pairs** to remove from $ P $ such that the speed limit is **constant** over all segments $ [i, i+1] $ for $ i \in [a, b-1] $.