题目描述

一个括号串的代价定义为：它的最长正则括号子序列的长度。

给定一个只包含 ( 和 ) 的字符串 $s$，以及整数 $k$。你可以删除最多 $k$ 个字符，使得删除后字符串的代价尽可能小。

请输出一个长度为 $n$ 的二进制串。第 $i$ 位为 1 表示删除 $s_i$，为 0 表示保留 $s_i$。如果有多种最优方案，输出任意一种。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试数据第一行包含两个整数 $n,k$。

第二行包含一个长度为 $n$ 的括号串 $s$。

输出格式

对每组测试数据，输出一个长度为 $n$ 的二进制串。输出中 1 的个数不能超过 $k$，且删除对应字符后得到的字符串代价必须最小。

数据范围

• $1 \le t \le 1000$
• $1 \le n \le 5000$
• $0 \le k \le n$
• 所有测试组的 $n$ 之和不超过 $5000$

3
2 1
)(
4 1
(())
6 2
()()()

00
1000
100001

提示

在第一个测试用例中，字符串的代价已经是 $0$，因此可以不进行任何删除。

在第三个测试用例中，无法通过一次删除得到代价为 $0$ 的字符串，但可以通过删除任意一个字符得到代价为 $2$ 的字符串。

来源

Codeforces Round 2233 C - Cost of a Bracket Sequence