U565586 括号匹配

给定一字符串，只由 `(`、`)` 和 `*` 三种字符组成，你需要替换掉所有的 `*` 使得整个字符串变为一个 平衡的括号串。你可以选择将一个 `*` 替换为一个 `(` 或 `)`，也可以直接删掉这个 `*`（也就是替换为一个 空串）。 一个平衡的括号串定义如下： 1. 空串是平衡的括号串。 2. 如果 $A,B$ 均为平衡的括号串，那么 $AB$ 也是一个平衡的括号串（这里 $AB$ 指将 $A$ 与 $B$ 拼接起来）。 3. 如果 $A$ 是一个平衡的括号串，那么 $(A)$ 也是一个平衡的括号串。 给定这样一个含有 `*` 的括号串，输出替换掉所有 `*` 后得到的一个平衡的括号串。由于可能存在多种答案，所以本题只要求选手输出**长度最短且字典序最小**的括号串。如果不能得到一个平衡的括号串，输出 `No solution!`。

输入仅一行，即一个字符串，只含有 `(`、`)` 以及 `*` 三种字符。

输出一行，即替换掉所有 `*` 后长度最短且字典序最小的平衡括号串。如果无解，输出 `No solution!`。

设字符串长度为 $n$。 对于 $20\%$ 的数据，有 $1\leq n\leq15$。 对于 $40\%$ 的数据，有 $1\leq n\leq10^3$。 对于 $100\%$ 的数据，有 $1\leq n\leq10^5$。