CF2233C.Cost of a Bracket Sequence

Let the cost of an arbitrary bracket string be the length of it's longest subsequence$^{\text{∗}}$ that is a regular bracket sequence$^{\text{†}}$.

You are given a bracket string $s$ and an integer $k$. Your task is to remove at most $k$ characters from the string $s$ so that the cost of the resulting string is minimized.

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

$^{\text{†}}$A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting the characters $+$ and $1$ into this sequence. For example, the sequences "$\texttt{(())()}$", "$\texttt{()}$", and "$\texttt{(()(()))}$" are regular, while "$\texttt{)(}$", "$\texttt{(()}$", and "$\texttt{(()))(}$" — are not.

定义任意括号串的代价为：其最长子序列（$^{\text{∗}}$）的长度，该子序列本身是一个合法括号序列（$^{\text{†}}$）。

给定一个括号串 $s$ 和一个整数 $k$。你的任务是从字符串 $s$ 中最多删除 $k$ 个字符，使得所得字符串的代价最小化。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中任意位置删除若干个（可能为零个或全部）元素而得到。

$^{\text{†}}$ 若能在该括号序列中插入字符 $+$ 和 $1$，从而得到一个合法的算术表达式，则称该括号序列是合法的。例如，串 "$\texttt{(())()}$"、"$\texttt{()}$" 和 "$\texttt{(()(()))}$" 是合法的；而 "$\texttt{)(}$"、"$\texttt{(()}$" 和 "$\texttt{(()))(}$" 则不是。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 5\,000$; $0 \le k \le n$) — the length of the string $s$ and the maximum number of deletions.

The second line of each test case contains a string $s$ of length $n$ consisting of the characters "$\texttt{(}$" and/or "$\texttt{)}$".

Additional input constraints:

• the sum of $n$ over all test cases does not exceed $5\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a binary string of length $n$. The $i$-th character should be equal to "1" if the corresponding character of the string $s$ is removed, and "0" otherwise.

The number of ones in the string must not exceed $k$. The cost of the string obtained after removing the marked characters must be as small as possible.

If there are several answers, output any of them.

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。其中第 $i$ 个字符应为 "1"，当且仅当字符串 $s$ 中对应位置的字符被删除；否则为 "0"。

该二进制字符串中 "1" 的个数不得超过 $k$。在删除被标记为 "1" 的字符后所得字符串的代价须尽可能小。

若存在多个满足条件的答案，输出任意一个即可。

In the first test case, the cost of the string is already $0$, so it is possible not to delete anything.

In the third test case, it is impossible to obtain a string of cost $0$ after one deletion, but it is possible to obtain a string of cost $2$ by deleting any character.

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

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