题目背景

2s 512M -O2

题目描述

你手里有两个长度均为 $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$？如果可以的话，你希望找到一个操作次数不太多的变换方案。

输入格式

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

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

对于每组数据而言：

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

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

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

输出格式

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

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

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

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

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

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

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

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

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

3
5 6
4 0
6 6

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

1
2 0
2
6 2
5 1

提示

【样例解释 #1】

在所有样例文件中，$\mathit{id}$ 均为 $0$。

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

$\texttt{(())()} \rightarrow \texttt{(())()()} \rightarrow \texttt{((()))()} \rightarrow \texttt{((()))}$

【数据范围】

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

对于 $100 \%$ 的数据，$1 \le T \le 3$，$1 \le n \le {10}^5$，$1 \le k \le 3 \times {10}^5$。

【提示】

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