I-组合积木_集美大学2024年团体程序设计天梯赛模拟赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

从左到右有 $n$ 个位置，编号为 $1$ 到 $n$ 。最开始每个位置上有一个积木，每个积木上有一个字符`(` 、`)` 或小写英文字母，给定 $m$ 次操作，操作类型分为三类：

操作 $1$ ：给定 $x$ 和 $y$ ，将位置 $x$ 上的积木按从上到下顺序取出，并按取出的顺序堆叠在位置 $y$ 所有积木的上方。
操作 $2$ ：给定 $x$ 和 $y$ ，将位置 $x$ 上的积木按从下到上顺序取出，并按取出的顺序堆叠在位置 $y$ 所有积木的上方。
操作 $3$ ：给定 $x$ ，将堆叠在位置 $x$ 上方的所有积木堆叠到各自初始位置所有积木的上方。

我们认为一个包含合法括号序列 $^{\dagger}$ 的字符串 $s$ ，通过从左到右按顺序匹配括号，可以从中得到若干个字符串，流程大致如下：

从左到右遍历字符串，直至遇到第一个`)`，假设位置为 $j$ 。
找到位于 $j$ 左边最近的`(`，假设位置为 $i(i < j)$ 。
记录区间 $(i, \ j)$ 构成的子串（若为空串则忽略），并将区间 $[i, \ j]$ 的子串从 $s$ 中删除，随后重复步骤 $1$ ，继续寻找下一个`)`。
在上述流程结束后，记录最后的 $s$ （若为空串则忽略）。

注：如果不太明白可以配合最下方例子进行理解。

现在要你在所有操作结束后，判断每个位置上积木从下往上将字符拼接得到的括号序列是否合法，并求出通过括号序列得到的结果。

$^{\dagger}$ 合法括号序列定义：
1. 空串是合法的括号序列。
2. 如果 $X$ 和 $Y$ 是合法的括号序列，那么 $XY$ 也是合法的括号序列。
3. 如果 $X$ 是合法的括号序列，那么 $(X)$ 也是合法的括号序列。
例如，`(())()`、`()`和`((()()))`是合法的括号序列，而`)(`、`(()`和`()(`则不是。

输入描述:

第一行给出两个整数  代表位置的数量和操作次数。

第二行  个字符，代表初始状态第  个位置积木上的字符。

随后  行，每行一个操作：`1 x y`、`2 x y`或`3 x`，其中第一个数字代表操作类型与题面描述一一对应，的含义与上述题面相同，保证 。

输出描述:

共  行，第  行代表第  个位置上从下往上连接得到的字符串通过括号序列得到的结果，若括号序列不合法，输出`-1`。否则先输出一个整数  代表第  个位置通过括号序列得到的字符串数量（忽略空串），随后  个字符串，按照得到的顺序输出，字符串之间以一个空格为间隔，行首行末无多余空格。

示例1

输入

复制

8 6
( a b ) ) b c (
2 3 2
1 2 1
1 4 1
1 6 7
2 7 5
3 5

输出

复制

1 ba
0
0
0
-1
1 b
1 c
-1

说明

样例解释：

第  次操作将位置  上的积木从下到上取出，并堆叠至位置 ，位置  上的积木从下到上分别为`a`、`b`。
第  次操作将位置  上的积木从上到下取出，并堆叠至位置 ，位置  上的积木从下到上分别为`(`、`b`、`a`。
第  次操作将位置  上的积木从上到下取出，并堆叠至位置 ，位置  上的积木从下到上分别为`(`、`b`、`a`、`)`。
第  次操作将位置  上的积木从上到下取出，并堆叠至位置 ，位置  上的积木从下到上分别为`c`、`b`。
第  次操作将位置  上的积木从下到上取出，并堆叠至位置 ，位置  上的积木从下到上分别为`)`、`c`、`b`。
第  次操作将位置  上的积木堆叠至原来的位置上，位置  上变为`)`、`b`、`c`。

括号匹配例子：

对于串`ab(abb(ab)a)c` ：
第一次配对发生在第  个字符`(` 和第  个字符`)` ，从两个括号中间可以得到第  个字符串`ab` ，随后将区间  的内容从串中删除，得到新串`ab(abba)c` 。
第二次配对发生在新串的第  个字符`(` 和第  个字符`)` ，从中可以得到第  个字符串`abba` ，将区间  的内容从串中删除，得到第  个字符串`abc` 。
最终字符串`ab` 、`abba` 、`abc` 就是字符串`ab(abb(ab)a)c` 通过括号序列从左到右匹配得到的结果。