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

满足下列条件之一的字符串被定义为**合法括号序列**。 - 空字符串。 - 对于某个合法括号序列 $A$，将 `(`、$A$ 和 `)` 按此顺序拼接得到的字符串。 - 将两个非空合法括号序列 $A$ 和 $B$ 按此顺序拼接得到的字符串。 设 $n$ 为正整数。对于长度为 $2n$ 的整数序列 $w=(w_1,w_2,\ldots,w_{2n})$，定义 $f(w)$ 如下。 对于长度为 $2n$ 的合法括号序列 $s=s_1s_2\ldots s_{2n}$，定义它相对于 $w$ 的得分 $w(s)$ 为所有满足 $s_i$ 为 `(` 的下标 $i$（$1\le i\le 2n$）对应的 $w_i$ 之和。令 $f(w)$ 为所有长度为 $2n$ 的合法括号序列 $s$ 的 $w(s)$ 的最大值。 给定一个正整数 $Q$。初始时，整数序列 $W$ 为空。 依次处理 $Q$ 次询问。第 $i$ 次询问给出整数 $t_i,x_i,y_i$。其中 $t_i$ 为 $1,2,3$ 之一，其含义如下： - 若 $t_i=1$：先在 $W$ 的开头插入 $x_i$，再在 $W$ 的开头插入 $y_i$。 - 若 $t_i=2$：先在 $W$ 的开头插入 $x_i$，再在 $W$ 的末尾插入 $y_i$。 - 若 $t_i=3$：先在 $W$ 的末尾插入 $x_i$，再在 $W$ 的末尾插入 $y_i$。 对于每次询问，求处理完该询问后的 $f(W)$。

输入包含一组或多组测试数据。第一行包含一个整数 $T$（$1\le T\le 10^5$），表示测试数据组数。每组测试数据的格式如下： ```text Q t_1 x_1 y_1 t_2 x_2 y_2 ... t_Q x_Q y_Q ``` 整数 $Q$（$1\le Q\le 4\times 10^5$）表示询问次数。 对于每个整数 $i$（$1\le i\le Q$），整数 $t_i,x_i,y_i$ 表示询问的内容。其中 $t_i$ 为 $1,2,3$ 之一，且 $|x_i|,|y_i|\le 10^7$。 所有测试数据的 $Q$ 之和不超过 $4\times 10^5$。

对于每组测试数据，输出 $Q$ 行。第 $i$ 行包含 $W$ 经过第 $i$ 次询问修改后的 $f(W)$。