#5437. 「OOI 2016 Day 2」邪恶联盟

题目描述

题目译自 $Open$ $Olympiad$ $in$ $Informatics$ $2016$ $Day2$ $T3$ 「Злая Лига Зла / The Evil League of Evil」。

邪恶马宣布招募邪恶联盟的成员！他在纸上用蹄子画了一条长长的字符串 $s$，字符串仅由字符 $(、)$ 和 $?$ 组成，并将其发送给了所有潜在的候选人。希望申请成为反派的候选人必须为每个 $?$ 字符选择将其替换为开括号 $($ 或闭括号 $)$。最终，能够在替换后的字符串中提取出最长的子序列作为合法括号序列的人，将被选入邪恶联盟。

子序列是指通过删除原字符串中一些（可能为零个）字符后得到的字符串。例如，字符串 $abc、ac、bcc$ 和 $abbcc$ 都是字符串 $abbcc$ 的子序列，而 $cb$ 和 $ba$ 则不是。注意，空字符串是任何字符串的子序列。

圆括号序列被称为合法的括号序列，当且仅当满足以下条件之一：

• 它是空的。
• 它是由一个合法的括号序列包裹在括号内构成的。
• 它是由两个合法的括号序列依次连接构成的。

例如，圆括号序列 $()()$ 和 $((()))()$ 是合法的，而 $)(()、((((($ 和 $())$ 则不是。

恐怖博士长期以来一直梦想加入邪恶联盟，但由于他的和平主义倾向，他并不擅长做恶事。恐怖博士解决问题的能力也不太强，因此他请求你帮助他完成邪恶马的难题。

输入格式

输入的唯一一行包含一个字符串 $s$ ($1 \leq |s| \leq 10000000$)。保证字符串 $s$ 仅由字符 $(、)$ 和 $?$ 组成。

输出格式

输出邪恶马问题的解，使得恐怖博士能够顺利加入邪恶联盟。即，将 $?$ 替换为 $($ 或 $)$，使得从替换后的字符串中能提取出的最长正确括号子序列的长度最大。如果存在多个最优解，可以输出其中任意一个。

样例 1

输入

?))?)

输出

()))()

在第一个样例中，替换后的字符串可以提取出长度为 $4$ 的正确括号子序列：$()()$。

样例 2

输入

)(???)( 

输出

)((())(

在第二个样例中，替换后的字符串可以提取出长度为 $4$ 的正确括号子序列：$(())$。注意，也可能存在其他答案。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。