有一天,小 Y 正在研究括号串。
“给出一个括号串,判断括号是否匹配。”
小 Y 说:“这不是傻×题吗?”。于是,小 Y 加强了一下:
“给出一个括号串,判断括号是否匹配,如果不匹配,请补全该括号串。”
例如:())[]]( 的一种补全方式为 (())[][]()
不一会儿,小 Y 解决了这道题,然而,他发现,这道题目有多种解法!但是他不会写 SPJ 了,于是他只好向你求助。
第一行一个正整数
,表示数据组数。
接下来每组数据,
第一行两个正整数,
。
第二行一个长度为的括号串
,表示原来的括号串。
第三行一个长度为的括号串
,表示补全后的括号串。
对于每组数据,如果是
的一种补全方式,输出 Accepted , 否则输出 Wrong Answer 。
注意:如果满足条件,并且存在长度为
的串
也满足条件,则
是也是符合条件的.
对于的数据,满足
。
对于另外的数据,满足
已经是一个匹配的括号串。
对于另外的数据 ,满足
。
对于的数据,满足
,并且
只包含 ( ,),[ 和 ] 。