题目描述

Little Mirko got a video game console for Christmas. It wasn’t a Playstation 4 or an Xbox one, but Atari 2600, and it came with one free game. The protagonist of the game is standing on the bottom of the screen, and there are various objects dispersed on the rest of the screen, falling towards the bottom.

More precisely, the screen can be represented as a grid of RxS pixels arranged in R rows and S columns. The protagonist takes up one pixel of the lowest line and is marked with ‘M’. The rest of the pixels are marked with some of the characters: ‘.’ (empty space), ‘*’ (bomb), ‘(‘ (open bracket) or ‘)’ (closed bracket).

The protagonist can move one pixel to the left or to the right in a single move, but doesn’t need to, whereas the rest of the objects simultaneously move one pixel down (possibly out of the screen). When the protagonist finds himself at the same position as one of the brackets, we say that he picked up that bracket and added it at the end of his array of acquired brackets. The protagonist’s goal is to acquire the longest possible valid bracket expression.

A valid bracket expression is defined inductively in the following way:

• “()” is a valid expression
• If a​ is a valid expression, then “(a​)” is a valid expression as well
• If a​ and b​ are valid expressions, then “ab​” is a valid expression as well

The game ends when the protagonist finds himself at the same position as the bomb, or when all the objects fall out of the screen.

输入格式

The first line of input contains the positive integers R ​and S ​(1 ≤ R, S ≤ 300) that represent the dimensions of the screen.

Each of the following R lines contains S characters ‘M’, ‘.’, ‘*’, ‘(‘ or ‘)’ that represent the initial state of the screen.

Test data will be such that there will always exist at least one valid bracket expression that is possible to acquire.

输出格式

In the first line, you must output the length of the longest valid bracket expression that Mirko can acquire.

In the second line, output that expression. If there are multiple longest valid expressions, output the lexicographically​ ​smallest​ one.

题目大意

题意翻译

Little Mirko 圣诞节获得了一台游戏机，它不是 Playstation 4 也不是 Xbox one，而是一台 Atari 2600，里面自带了一个这样的游戏：主角站在屏幕底部，天上有各种物体掉下来……

准确地说，屏幕可以看做 $R$ 行 $S$ 列的网格，主角站在最后一行，所在的位置标记为 M。其他格子上的标记可能是：.（空位置），*（炸弹），(（左括号）或 )（右括号）。

主角一次可以向左或向右移动一格，也可以不动，同时其他的物体向下落一格（可以掉出屏幕）。当主角与某括号位置相同时，他就捡起这个括号，放进他的括号序列尾部。游戏的目的是要获得最长的合法括号表达式。

合法的括号表达式是按下面方式归纳定义的：

• $\texttt{()}$ 是合法的括号表达式
• 如果 $a$ 是合法的括号表达式，那么 $\texttt{(}a\texttt{)}$ 也是合法的括号表达式。
• 如果 $a$ 和 $b$ 都是合法的括号表达式，那么 $ab$ 也是合法的括号表达式。

当所有物体掉出屏幕或者主角碰到炸弹（与炸弹在相同位置）时游戏结束。

5 4
..).
.)(.
(.)*
*(.*
..M.

4
(())

6 3
)(.
*..
(**
)()
().
M..

4
()()

6 3
((.
*..
(**
)()
().
M..

2
()

提示

In test cases worth 25% of total points, it will hold 1 ≤ R ≤ 15.

In test cases worth 50% of total points, it will hold 1 ≤ R ≤ 100.

If you output the correct length, but the wrong expression, you will be awarded 40% of points for that test case. In any case, in order to score points, your output must consist of two non-empty lines. (但我并不会做spj，所以这话屁用没有)

Clarification​ ​of​ ​the​ ​first​ ​test​ ​case:​ ​The protagonist’s moves are: left, left, right right.

Clarification​ ​of​ ​the​ ​second​ ​test​ ​case:​ ​The protagonist’s moves are: stay still, stay still, stay still, right, left.

Clarification​ ​of​ ​the​ ​third​ ​test​ ​case:​ ​The protagonist’s moves are: stay still, stay still, right.