小 Mirko 在圣诞节收到了一台游戏机。它不是 Playstation 4，也不是 Xbox One，而是 Atari 2600，并且附赠了一款免费游戏。游戏的主角站在屏幕的最下方，而屏幕的其他地方散落着各种物体，它们正向底部坠落。
更具体地说，屏幕可以表示为一个由 $R$ 行 $S$ 列组成的 $R \times S$ 像素网格。主角占据最底下一行的一个像素，并用字符 'M' 表示。其余像素用以下字符之一表示：'.'（空地）、'*'（炸弹）、'('（左括号）或 ')'（右括号）。
在单次移动中，主角可以向左或向右移动一个像素，也可以选择不移动（保持原地不动）。与此同时，屏幕上的其他所有物体同时向下移动一个像素（可能会移出屏幕）。当主角与某个括号处于相同位置时，我们称他捡起了该括号，并将其添加到他已获得的括号序列的末尾。主角的目标是获得尽可能长的合法括号序列。
合法括号序列的归纳定义如下：
- “()” 是一个合法序列
- 如果 $a$ 是一个合法序列，那么 “(a)” 也是一个合法序列
- 如果 $a$ 和 $b$ 是合法序列，那么 “ab” 也是一个合法序列
当主角与炸弹处于相同位置，或者所有物体都落出屏幕时，游戏结束。
输入格式
第一行包含两个正整数 $R$ 和 $S$ ($1 \le R, S \le 300$)，表示屏幕的尺寸。
接下来的 $R$ 行，每行包含 $S$ 个字符，字符为 'M'、'.'、'*'、'(' 或 ')' 之一，表示屏幕的初始状态。
测试数据保证至少存在一个可以获得的合法括号序列。
输出格式
第一行输出 Mirko 可以获得的最长合法括号序列的长度。
第二行输出该序列。如果有多个最长的合法序列，输出其中字典序最小的一个。
子任务
在占总分 25% 的测试数据中，满足 $1 \le R \le 15$。
在占总分 50% 的测试数据中，满足 $1 \le R \le 100$。
如果你输出的长度正确，但序列错误，你将获得该测试点 40% 的分数。在任何情况下，为了获得分数，你的输出必须包含两个非空行。
样例
输入 1
5 4 ..). .)(. (.)* *(.* ..M.
输出 1
4 (())
输入 2
6 3 )(. *.. (** )() (). M..
输出 2
4 ()()
输入 3
6 3 ((. *.. (** )() (). M..
输出 3
2 ()
说明
样例 1 说明
主角的移动轨迹为：左、左、右、右。
样例 2 说明
主角的移动轨迹为：原地不动、原地不动、原地不动、右、左。
样例 3 说明
主角的移动轨迹为：原地不动、原地不动、右。