Longest Valid Bracket Expression

Little Mirko received an old Atari 2600 for Christmas along with a quirky game. The game screen is represented by an R×S grid where each pixel can be empty (denoted by .), contain a bomb (*), or have a bracket (( or )). The protagonist, denoted by M, stands on the bottom row. All other objects (bombs and brackets) occupy the other rows.

When the game begins, at every turn the following happens simultaneously:

• The protagonist may move one pixel to the left, one pixel to the right, or remain in the same column (but cannot move beyond the grid boundaries).
• All objects on the grid move one pixel downward. An object originally at row r will reach the bottom row at time t = R - 1 - r (using 0-indexed rows) if it has not fallen off already.

If, after moving, the protagonist is in the same column where an object has just reached the bottom row, the following occurs immediately:

• If the object is a bomb (*), the game immediately ends. (The bomb is not collected.)
• If the object is a bracket (( or )), the bracket is collected and appended to the end of a sequence of acquired brackets.
• If the cell contains a dot (.), nothing is collected.

The goal is to plan the protagonist’s moves so that the final collected bracket sequence is a valid bracket expression of maximum possible length. A valid bracket expression is defined inductively as follows:

• Base: () is a valid expression.
• Recursion: If \(a\) is a valid expression, then \( (a) \) is also valid.
• Concatenation: If \(a\) and \(b\) are valid expressions, then their concatenation \(ab\) is valid.

Important: The bracket is collected automatically when encountered. Note that if the protagonist ever steps onto a bomb, the game ends immediately and no further moves are allowed. Also, if no non-empty valid expression can be collected, output 0.

inputFormat

The first line contains two integers R and S representing the number of rows and columns, respectively.

The next R lines each contain a string of S characters. The grid is represented as follows:

• M: The protagonist (present only in the bottom row).
• .: Empty pixel.
• *: Bomb (stepping on this ends the game immediately).
• ( or ): Brackets.

outputFormat

Output the longest valid bracket expression that can be collected by the protagonist along some valid path. If no non-empty valid expression can be collected, output 0.

sample

3 3
(()
(()
.M.

()