정사각형 모양의 기록판이 하나 있다. 이 기록판은 N × N개의 칸으로 이루어져 있으며, 각 칸에는 0 또는 1 중 하나의 문자가 적혀 있다.

이 기록판을 짧은 문자열로 옮겨 적으려고 한다. 문자열을 만드는 방법은 다음과 같다.

먼저 현재 보고 있는 정사각형 영역 안의 모든 문자가 같은지 확인한다.

• 영역 안의 문자가 전부 0이라면, 이 영역은 하나의 문자 0으로 나타낸다.

• 영역 안의 문자가 전부 1이라면, 이 영역은 하나의 문자 1로 나타낸다.

• 두 종류의 문자가 함께 들어 있다면, 이 영역은 하나의 문자로 나타낼 수 없다.

하나의 문자로 나타낼 수 없는 경우에는, 현재 영역을 크기가 같은 네 개의 정사각형 영역으로 나눈다.

나누어진 영역들은 다음 순서로 다시 같은 방식으로 문자열로 바꾼다.

1. 왼쪽 위 영역
2. 오른쪽 위 영역
3. 왼쪽 아래 영역
4. 오른쪽 아래 영역

그리고 네 영역에서 얻은 문자열을 차례대로 이어 붙인 뒤, 그 전체를 괄호로 감싸서 나타낸다.

즉, 어떤 영역을 한 문자로 줄일 수 있으면 그대로 0 또는 1을 쓰고, 그렇지 않으면 네 부분의 결과를 순서대로 괄호 안에 묶어 쓴다.

N × N 크기의 기록판이 주어졌을 때, 위 규칙에 따라 만들어지는 문자열을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 기록판의 크기를 나타내는 숫자 N이 주어진다.

N은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다.

두 번째 줄부터는 길이 N의 문자열이 N개 들어온다.

각 문자열은 0 또는 1로만 이루어져 있으며, 기록판의 각 칸에 적힌 문자를 나타낸다.

출력

주어진 기록판을 규칙에 따라 문자열로 나타낸 결과를 출력한다.

예제 입력 1

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1

((110(0101))(0010)1(0001))