Johnny 喜欢秩序，非常讨厌杂乱无章的括号。最近他看到了一个字符串 ){(，这让他很烦恼，因为这不是一个合法的括号序列。幸运的是，Johnny 口袋里有一支笔，他可以在开头添加 (，在末尾添加 )}。这样他就能安然入睡了，因为字符串变成了 (){()}，这是一个合法的括号序列。

Johnny 把修复括号序列作为了他一生的使命。他将通过在发现的序列开头和末尾添加新的括号来使它们变得合法。由于他的笔快没墨水了，Johnny 希望添加尽可能少数量的括号来达到这个目的。帮帮他吧！编写一个程序，读取一个括号序列，要么计算出修复后可能的最短合法括号序列并将其输出，要么说明无法将其修复。

合法的括号序列递归定义如下：

• 空序列是一个合法的括号序列；
• 如果 $S$ 和 $T$ 是合法的括号序列，那么它们的拼接 $ST$ 也是一个合法的括号序列；
• 如果 $S$ 是一个合法的括号序列，那么 $(S)$、$[S]$ 和 $\{S\}$ 也都是合法的括号序列。

输入格式

输入仅有一行，包含一个非空的括号序列，由字符 (, ), [, ], {, } 组成，长度最多为 $1\,000\,000$。这是 Johnny 想要修复的括号序列。

输出格式

输出应包含修复后的输入序列。如果有多种可能的方法可以使修复后的序列达到相同的最短长度，输出其中任意一种即可。

如果无法修复该输入序列，输出单词 NIE。

样例

输入样例 1

){(

输出样例 1

(){()}

输入样例 2

(}

输出样例 2

NIE

说明

第一个样例即为题目描述中的例子。

在第二个样例中，序列无法被修复。