P17543 [JAG 2026 Summer Camp #2] Deque Bracket Optimization

A string satisfying one of the following conditions is defined as a **correct parenthesis sequence**. - The empty string. - A string obtained by concatenating `(`, $A$, and `)` in this order for some correct parenthesis sequence $A$. - A string obtained by concatenating $A$ and $B$ in this order, where $A$ and $B$ are nonempty correct parenthesis sequences. Let $n$ be a positive integer. For an integer sequence $w=(w_1,w_2,\ldots,w_{2n})$ of length $2n$, define $f(w)$ as follows. For a correct parenthesis sequence $s=s_1s_2\ldots s_{2n}$ of length $2n$, define its score $w(s)$ with respect to $w$ as the sum of $w_i$ over all $i$ ($1\le i\le 2n$) such that $s_i$ is `(`. Let $f(w)$ be the maximum value of $w(s)$ over all correct parenthesis sequences $s$ of length $2n$. You are given a positive integer $Q$. Initially, the integer sequence $W$ is empty. Process $Q$ queries in order. In the $i$-th query, you are given integers $t_i,x_i,y_i$. Here, $t_i$ is one of $1,2,3$ and indicates the following: - If $t_i=1$: prepend $x_i$ to $W$, and then prepend $y_i$ to $W$. - If $t_i=2$: prepend $x_i$ to $W$, and then append $y_i$ to $W$. - If $t_i=3$: append $x_i$ to $W$, and then append $y_i$ to $W$. For each query, find $f(W)$ after the query has been processed.

The input consists of one or more test cases. The first line of the input contains an integer $T$ ($1\le T\le 10^5$), the number of test cases. Each of the $T$ test cases is given in the following format: ```text Q t_1 x_1 y_1 t_2 x_2 y_2 ... t_Q x_Q y_Q ``` The integer $Q$ ($1\le Q\le 4\times 10^5$) represents the number of queries. For each integer $i$ ($1\le i\le Q$), the integers $t_i,x_i,y_i$ represent the contents of the query. Here, $t_i$ is one of $1,2,3$, and $|x_i|,|y_i|\le 10^7$. The sum of $Q$ over all test cases does not exceed $4\times 10^5$.

For each of the $T$ test cases, print $Q$ lines. The $i$-th line should contain $f(W)$ after $W$ has been modified by the $i$-th query.