Background

$\large{\bf{{Warning: abusing the judging for this problem, even once, will result in a ban.}}}$

Problem Description

We define a merge of strings $s$ and $t$ as any string obtained by interleaving the characters of $s$ and $t$. In other words, after merging, the characters can be colored using two colors such that reading only the characters of one color gives exactly string $s$, and reading only the characters of the other color gives exactly string $t$.

A string $w$ consisting of left parentheses $\texttt{(}$ and right parentheses $\texttt{)}$ is called a valid bracket expression if the number of left parentheses in $w$ equals the number of right parentheses, and in every prefix of $w$, the number of left parentheses is at least the number of right parentheses.

You are given two bracket strings $s$ and $t$. Compute how many pairs $1 \le i \le j \le |t|$ satisfy the following: there exists a valid bracket expression $w$ such that $w$ is a merge of string $s$ and string $t[i \dots j]$ (i.e., the non-empty substring of $t$ from position $i$ to position $j$).

Input Format

The first line contains string $s$, and the second line contains string $t$.

To avoid excessively large input, each string is given in the following form:

Each line starts with an integer $n$ ($1 \le n \le 100\ 000$), followed by a character $c$ (either $\texttt{(}$ or $\texttt{)}$), and then a sequence of $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 1\ 000\ 000$). The string encoded in this way starts with character $c$ repeated $a_1$ times, then the other type of parenthesis repeated $a_2$ times, then character $c$ repeated $a_3$ times, and so on.

Output Format

Output one integer: the number of pairs $(i, j)$ that satisfy the condition, i.e., the number of pairs such that some merge of string $s$ and substring $t[i \dots j]$ is a valid bracket expression.

3 ( 1 3 1
3 ) 1 3 2

3

2 ( 1 1
4 ) 2 1 1 2

4

Hint

Sample 1 explanation: The strings described in this sample are $\texttt{()))(}$ and $\texttt{)((()))}$. From the second string, we can take the substrings $\texttt{)((()}$, $\texttt{((()))}$, or $\texttt{(()}$.
In the first case, one valid merge of string $\colorbox{DDDDDD}{\texttt{()))(}}$ and substring $\colorbox{BBBBBB}{\texttt{)((()}}$ is $\colorbox{DDDDDD}{\texttt{(}}\colorbox{BBBBBB}{\texttt{)(((}}\colorbox{DDDDDD}{\texttt{)))(}}\colorbox{BBBBBB}{\texttt{)}}$.

Sample 2 explanation: The strings described in this sample are $\texttt{()}$ and $\texttt{))()((}$. Note that although the substring from the second character to the third character and the substring from the fourth character to the fifth character are the same substring $\texttt{)(}$, we still count it twice. Although the string $\texttt{()}$ itself is a valid bracket expression, the empty substring is not included in the count.

Translated by ChatGPT 5