A shuffle of words $s$ and $t$ is any word formed by interleaving the letters of $s$ and $t$. In other words, the letters in the shuffle can be colored with two colors such that reading only the letters of one color yields exactly the word $s$, and reading only the letters of the other color yields exactly the word $t$.

A word $w$ consisting of opening '(' and closing ')' parentheses is called a valid parenthesis expression if the number of opening parentheses in $w$ is equal to the number of closing parentheses, and in every prefix of $w$, the number of opening parentheses is not less than the number of closing parentheses.

Given two words $s$ and $t$ composed of parentheses, calculate how many pairs $1 \le i \le j \le |t|$ exist such that there is a valid parenthesis expression $w$ which is a shuffle of the word $s$ and the substring $t[i \dots j]$ (i.e., a non-empty fragment of the word $t$ from position $i$ to position $j$).

Input

The first line of input contains the representation of word $s$, and the second line contains the representation of word $t$.

Each of these lines starts with an integer $n$ ($1 \le n \le 100\,000$), followed by a character $c$ which is one of the parentheses '(' or ')', and then a sequence of $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$). The word encoded in this way starts with the character $c$ repeated $a_1$ times, followed by the other type of parenthesis repeated $a_2$ times, then the character $c$ repeated $a_3$ times, and so on.

Output

Output a single integer — the number of pairs $(i, j)$ for which some shuffle of the word $s$ and the substring $t[i \dots j]$ is a valid parenthesis expression.

Examples

Input 1

3 ( 1 3 1
3 ) 1 3 2

Output 1

3

Note 1

The words described by this example are ()))( and )((()). From the second word, we can take the fragment )((() or ((()), or ((). In the first case, a valid shuffle of the word ()))( and the fragment )((() is ( )((( )))( ).

Input 2

2 ( 1 1
4 ) 2 1 1 2

Output 2

4

Note 2

The words described by this example are () and ))()((. Note that although the fragments from the second to the third and from the fourth to the fifth letters result in the same substring )(, we count them twice. Even though the word () itself is a valid parenthesis expression, we do not count empty fragments of the second word.