레트로

미르코가 크리스마스 선물로 비디오 게임기를 받았다. 플레이스테이션 4나 엑스박스 원이 아니라 아타리 2600이었고, 게임 하나가 딸려 왔다. 게임의 주인공은 화면 맨 아래에 서 있고, 화면의 나머지 부분에는 여러 물체가 흩어져 아래로 떨어진다.

화면은 $R$개의 행과 $S$개의 열로 이루어진 $R \times S$ 픽셀 격자다. 주인공은 맨 아랫줄의 픽셀 한 칸을 차지하며 M으로 표시한다. 나머지 픽셀은 .(빈 칸), *(폭탄), ((여는 괄호), )(닫는 괄호) 중 하나로 표시한다.

한 번의 이동에서 주인공은 왼쪽이나 오른쪽으로 한 픽셀 움직일 수 있고, 움직이지 않아도 된다. 같은 시각에 나머지 물체는 모두 아래로 한 픽셀 내려가며, 화면 밖으로 나가기도 한다. 주인공이 괄호와 같은 위치에 놓이면 그 괄호를 주웠다고 하고, 지금까지 모은 괄호 배열의 끝에 그 괄호를 덧붙인다. 주인공의 목표는 가능한 한 긴 올바른 괄호 수식을 모으는 것이다.

올바른 괄호 수식은 다음과 같이 귀납적으로 정의한다.

• ()는 올바른 수식이다.
• $a$가 올바른 수식이면 $(a)$도 올바른 수식이다.
• $a$와 $b$가 올바른 수식이면 $ab$도 올바른 수식이다.

주인공이 폭탄과 같은 위치에 놓이거나 모든 물체가 화면 밖으로 떨어지면 게임이 끝난다.

첫째 줄에 화면의 크기를 나타내는 양의 정수 $R$, $S$가 주어진다. ($1 \le R, S \le 300$)

다음 $R$개 줄에는 화면의 처음 상태를 나타내는 문자가 한 줄에 $S$개씩 주어진다. 각 문자는 M, ., *, (, ) 중 하나다.

입력 자료에서 주인공이 모을 수 있는 올바른 괄호 수식은 항상 하나 이상 존재한다.

첫째 줄에 미르코가 모을 수 있는 가장 긴 올바른 괄호 수식의 길이를 출력한다.

둘째 줄에 그 수식을 출력한다. 길이가 가장 긴 올바른 괄호 수식이 여러 개이면 사전순으로 가장 앞서는 것을 출력한다.

첫 번째 예제에서 주인공의 이동은 왼쪽, 왼쪽, 오른쪽, 오른쪽이다.

두 번째 예제에서 주인공의 이동은 제자리, 제자리, 제자리, 오른쪽, 왼쪽이다.

세 번째 예제에서 주인공의 이동은 제자리, 제자리, 오른쪽이다.