我们将两个字符串 $s$ 和 $t$ 的交错（splot）定义为通过交织 $s$ 和 $t$ 的字符所形成的任何字符串。换句话说，交错字符串中的字符可以被涂成两种颜色，使得只读取其中一种颜色的字符时，恰好得到字符串 $s$，而只读取另一种颜色的字符时，恰好得到字符串 $t$。

由左括号 ( 和右括号 ) 组成的字符串 $w$ 被称为合法括号序列，当且仅当 $w$ 中左括号的数量等于右括号的数量，且在 $w$ 的任何前缀中，左括号的数量不小于右括号的数量。

给定两个由括号组成的字符串 $s$ 和 $t$。请计算有多少对 $1 \le i \le j \le |t|$，使得存在一个字符串 $w$ 是 $s$ 与 $t[i \dots j]$（即字符串 $t$ 从位置 $i$ 到位置 $j$ 的非空子串）的交错，且 $w$ 是一个合法括号序列。

输入格式

输入的第一行包含字符串 $s$ 的描述，第二行包含字符串 $t$ 的描述。

每一行以一个整数 $n$ ($1 \le n \le 100\,000$) 开头，随后是一个字符 $c$（为 ( 或 ) 之一），接着是 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$)。以此方式编码的字符串以字符 $c$ 开头，该字符重复 $a_1$ 次，接着是重复 $a_2$ 次的另一种括号，再接着是重复 $a_3$ 次的字符 $c$，依此类推。

输出格式

输出一个整数，表示满足条件的对 $(i, j)$ 的数量，即使得 $s$ 与 $t[i \dots j]$ 的某种交错为合法括号序列的对数。

样例

样例输入 1

3 ( 1 3 1
3 ) 1 3 2

样例输出 1

3

说明 1

该示例描述的字符串为 ()))( 和 )((())。从第二个字符串中，我们可以取片段 )((() 或 ((()) 或 (()。 在第一种情况下，()))( 和片段 )((() 的一个合法交错是 ( )((( )))( )。

样例输入 2

2 ( 1 1
4 ) 2 1 1 2

样例输出 2

4

说明 2

该示例描述的字符串为 () 和 ))()((。请注意，尽管从第二到第三个字符的片段和从第四到第五个字符的片段都给出了相同的子串 )(，但我们将其计算两次。尽管字符串 () 本身是一个合法括号序列，但我们不计算第二个字符串的空片段。