#WC2022A. 序列变换

序列变换

题目描述

你手里有两个长度均为 2n2n 的合法括号序列 s1,s2s_1, s_2

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

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

形式化地,这 44 种变换操作如下:

  • 操作 11 :将形如 p(((A)B)C)q\texttt{p(((A)B)C)q} 的串变换为 p((A)B)(C)q\texttt{p((A)B)(C)q} (其中 p,q\texttt{p,q} 为任意串,可以为空,但不一定分别为合法括号序列,下同);
  • 操作 22 :将形如 p((A)(B)C)q\texttt{p((A)(B)C)q} 的串变换为 p((A)B)(C)q\texttt{p((A)B)(C)q}
  • 操作 33 :将形如 p(A)((B)C)q\texttt{p(A)((B)C)q} 的串变换为 p((A)B)(C)q\texttt{p((A)B)(C)q}
  • 操作 44 :将形如 p(A)(B)(C)q\texttt{p(A)(B)(C)q} 的串变换为 p((A)B)(C)q\texttt{p((A)B)(C)q}

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

  • 操作 55 :将形如 pq\texttt{pq} 的串变换为 p()q\texttt{p()q}
  • 操作 66 :将形如 p()q\texttt{p()q} 的串变换为 pq\texttt{pq}

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

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

你现在想知道的是:凭借上述操作,能否将 s1s_1 变换为 s2s_2?如果可以的话,你希望找到一个操作次数不太多的变换方案。

输入格式

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

11 行:22 个正整数 id,Tid,T,分别表示测试点编号和数据组数。其中测试点编号可以帮助你判断测试点的特殊条件。

对于每组数据而言:

11 行:两个正整数 n,kn,k ,其中 kk 表示你的操作步数的上限。

22 行:一个长度为 2n2n 的括号序列 s1s_1

33 行:一个长度为 2n2n 的括号序列 s2s_2

输出格式

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

每组数据的第 11 行,一个整数 mm ,表示你的操作次数。需要保证 mkm \leq k

接下来 mm 行,每行输出 22 个非负整数 op x\text{op x} ,描述一个操作。

其中 opop 为当前操作的编号,需满足 1op61 \leq op \leq 6xx 描述此次操作的位置,为方便起见,统一定义为形式化描述中 pp 的长度。

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

同时你需要保证,每组数据中操作 5566 的使用次数分别不得超过 22 次,有特殊说明的子任务除外。

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

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

0 1
3 6
(())()
((()))
3
5 6
4 0
6 6

样例 1 解释

在所有样例文件中,idid 均为 00

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

(())()
(())()()
((()))()
((()))
0 2
3 10
(()())
(())()
4 20
((()))()
(()())()
1
2 0
2
6 2
5 1

数据范围

对所有测试点,T3T\le 3n105n\le 10^5k3×105k\le 3\times 10^5。每个测试点的具体限制见下表。

测试点编号 nn\leq k=k= 特殊条件
131\sim 3 1010 10410^4
464\sim 6 100100 10510^5
787\sim 8 500500 10410^4 操作 5,65,6 可以使用任意多次
9119\sim 11 10001000 10510^5
121312\sim 13 50005000 10410^4
141614\sim 16 10510^5 2×1042\times 10^4 操作 5,65,6 可以使用任意多次
172017\sim 20 3×1053\times 10^5

提示

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

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