题目描述

你手里有两个长度均为 $2n$ 的合法括号序列 $s_1, s_2$。

在你眼中，不同的括号序列带来的视觉美感不尽相同。因此，你对具有某一种结构的括号序列特别喜欢，而讨厌具有其他一些结构的括号序列。你希望对 $s_1$ 进行一些变换，以消除掉一些自己不喜欢的结构。

具体而言，形如 $\texttt{((A)B)(C)}$（其中 $\texttt{A,B,C}$ 均为合法括号序列，下同）的结构是你喜欢的，而如下几种则是不喜欢的：$\texttt{(((A)B)C)}$ 、$\texttt{((A)(B)C)}$ 、$\texttt{(A)((B)C)}$ 和 $\texttt{(A)(B)(C)}$ 。相应地，你有 $4$ 种变换操作，分别表示取出原括号序列中的一个你不喜欢的子串，并将其变换为你喜欢的结构后放回原位置。

形式化地，这 $4$ 种变换操作如下：

• 操作 $1$ ：将形如 $\texttt{p(((A)B)C)q}$ 的串变换为 $\texttt{p((A)B)(C)q}$ （其中 $\texttt{p,q}$ 为任意串，可以为空，但不一定分别为合法括号序列，下同）；
• 操作 $2$ ：将形如 $\texttt{p((A)(B)C)q}$ 的串变换为 $\texttt{p((A)B)(C)q}$；
• 操作 $3$ ：将形如 $\texttt{p(A)((B)C)q}$ 的串变换为 $\texttt{p((A)B)(C)q}$；
• 操作 $4$ ：将形如 $\texttt{p(A)(B)(C)q}$ 的串变换为 $\texttt{p((A)B)(C)q}$；

另外，你还希望拥有一些能够改变字符串长的操作，于是你希望能够在字符串中任意位置插入一对括号 $\texttt{()}$ ，或者将任意位置的一对括号 $\texttt{()}$ 删除，形式化描述如下：

• 操作 $5$ ：将形如 $\texttt{pq}$ 的串变换为 $\texttt{p()q}$；
• 操作 $6$ ：将形如 $\texttt{p()q}$ 的串变换为 $\texttt{pq}$；

但由于一些限制条件，你执行上述两条操作的次数最多分别不超过 $2$ 次（部分子任务中无此限制条件，详见数据范围部分）。

容易证明，对于任意合法括号序列实行上述 $6$ 种操作之一，得到的仍为合法括号序列。

你现在想知道的是：凭借上述操作，能否将 $s_1$ 变换为 $s_2$？如果可以的话，你希望找到一个操作次数不太多的变换方案。

输入格式

每个测试点由多组数据组成。

第 $1$ 行：$2$ 个正整数 $id,T$，分别表示测试点编号和数据组数。其中测试点编号可以帮助你判断测试点的特殊条件。

对于每组数据而言：

第 $1$ 行：两个正整数 $n,k$ ，其中 $k$ 表示你的操作步数的上限。

第 $2$ 行：一个长度为 $2n$ 的括号序列 $s_1$。

第 $3$ 行：一个长度为 $2n$ 的括号序列 $s_2$。

输出格式

对于每组数据分别输出若干行：

每组数据的第 $1$ 行，一个整数 $m$ ，表示你的操作次数。需要保证 $m \leq k$。

接下来 $m$ 行，每行输出 $2$ 个非负整数 $\text{op x}$ ，描述一个操作。

其中 $op$ 为当前操作的编号，需满足 $1 \leq op \leq 6$；$x$ 描述此次操作的位置，为方便起见，统一定义为形式化描述中 $p$ 的长度。

你需要确保给出的 $\text{op x}$ 确实能描述一个符合要求的操作；在此基础上，可以证明所有符合要求的操作可以由 $\text{op x}$ 唯一确定。

同时你需要保证，每组数据中操作 $5$ 和 $6$ 的使用次数分别不得超过 $2$ 次，有特殊说明的子任务除外。

如果有多种变换方案符合要求，输出任意一种即可。

特别地，如果该组数据无法在 $k$ 步之内实现变换，你只需要对于该组数据输出一个 $-1$ 即可。

0 1
3 6
(())()
((()))

3
5 6
4 0
6 6

样例 1 解释

在所有样例文件中，$id$ 均为 $0$。

本组数据的变换过程如下：

(())()
(())()()
((()))()
((()))

0 2
3 10
(()())
(())()
4 20
((()))()
(()())()

1
2 0
2
6 2
5 1

数据范围

对所有测试点，$T\le 3$，$n\le 10^5$，$k\le 3\times 10^5$。每个测试点的具体限制见下表。

测试点编号	$n\leq$	$k=$	特殊条件
$1\sim 3$	$10$	$10^4$	无
$4\sim 6$	$100$	$10^5$
$7\sim 8$	$500$	$10^4$	操作 $5,6$ 可以使用任意多次
$9\sim 11$	$1000$	$10^5$	无
$12\sim 13$	$5000$	$10^4$
$14\sim 16$	$10^5$	$2\times 10^4$	操作 $5,6$ 可以使用任意多次
$17\sim 20$		$3\times 10^5$	无

提示

请点击题目右侧“文件”选项下载本题样例。

称一个字符串 $s$ 为合法括号序列，当且仅当 $s$ 仅由相等数量的字符 ( 和字符 ) 组成，且对于 $s$ 的每一个前缀而言，( 的数量均不少于 ) 的数量，特别地，空串也是合法括号序列。