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.

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 $ .

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.

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.