令任意括号字符串的成本为其最长子序列$$$^{\text{*}}$$$的长度,该子序列是常规括号序列$$$^{\text{†}}$$$。
给你一个括号字符串 $$$s$$$ 和一个整数 $$$k$$$。您的任务是从字符串 $$$s$$$ 中删除最多 $$$k$$$ 个字符,以便最小化生成字符串的成本。
$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。
$$$^{\text{†}}$$$如果可以通过将字符 $$$+$$$ 和 $$$1$$$ 插入该序列来获得正确的算术表达式,则该括号序列称为正则括号序列。例如,序列“$$$\texttt{(())()}$$$”、“$$$\texttt{()}$$$”和“$$$\texttt{(()(()))}$$$”是常规序列,而“$$$\texttt{)(}$$$”、“$$$\texttt{(()}$$$”和“$$$\texttt{(()))(}$$$”——不是。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 5\,000$$$; $$$0 \le k \le n$$$) - 字符串 $$$s$$$ 的长度和最大删除次数。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“$$$\texttt{(}$$$”和/或“$$$\texttt{)}$$$”组成。
附加输入限制:
- 所有测试用例的 $$$n$$$ 总和不超过 $$$5\,000$$$。
输出
对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串。第 $$$i$$$ 个字符应等于“1"如果字符串$$$s$$$对应的字符被删除,并且"0”否则。
字符串中 1 的数量不得超过 $$$k$$$。去掉标记字符后得到的字符串的代价必须尽可能小。
如果有多个答案,则输出其中任何一个。
示例
输入复制
102 1)(2 0()4 1(())4 1())(5 1((())6 2()()()6 2(()())6 2())(()7 3(()((()10 3(()())())(
输出复制
00 00 1000 1000 00010 101000 001001 100001 1100001 0101001000
注意
在第一个测试用例中,字符串的成本已经是 $$$0$$$,因此可以不删除任何内容。
在第三个测试用例中,一次删除后不可能得到成本$$$0$$$的字符串,但是删除任意字符都可以获得成本$$$2$$$的字符串。