Пусть стоимость произвольной скобочной строки — это длина её максимальной подпоследовательности$$$^{\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$$$ и максимальное количество удалений.
Во второй строке каждого набора входных данных содержится $$$s$$$ длины $$$n$$$ и состоящая из символов «$$$\texttt{(}$$$» и «$$$\texttt{)}$$$».
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите бинарную строку длины $$$n$$$. $$$i$$$-й символ должен быть равен «1», если соответствующий символ строки $$$s$$$ удаляется, и «0» иначе.
Количество единиц в строке не должно превышать $$$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$$$, удалив любой символ.
