← 返回题目列表

Codeforces · 1023/C

C. 括号子序列

中文机器翻译题面 查看原题

括号序列是仅包含字符“(”和“)”的字符串。正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”,可以将括号序列转化为正确的算术表达式。例如,括号序列“()()”和“(())”是正规的(结果表达式是:“(1)+(1)”和“((1+1)+1)”),而“)(”、“(”和“)”则不是。

子序列是可以通过删除某些元素而不改变剩余元素的顺序从另一个序列导出的序列。

给你一个常规括号序列 $$$s$$$ 和一个整数 $$$k$$$。你的任务是找到一个长度恰好为 $$$k$$$ 的正则括号序列,使其也是 $$$s$$$ 的子序列。

保证这样的序列总是存在。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$($$$2 \le k \le n \le 2 \cdot 10^5$$$,$$$n$$$ 和 $$$k$$$ 都是偶数)——$$$s$$$ 的长度和要求查找的序列的长度。

第二行是一个字符串 $$$s$$$ — 长度为 $$$n$$$ 的常规括号序列。

输出

打印单个字符串 - 长度恰好为 $$$k$$$ 的常规括号序列,因此它也是 $$$s$$$ 的子序列。

保证这样的序列总是存在。

示例

输入 #1

6 4
()(())

输出 #1

()()

输入 #2

8 8
(()(()))

输出 #2

(()(()))