흑백 영상은 각 칸이 검은색 또는 흰색인 정사각형 격자로 나타낼 수 있다. 영상이 커지면 모든 칸을 그대로 저장하는 대신, 같은 색으로 채워진 영역을 하나의 기호로 줄여 저장하는 편이 효율적이다.

이 문제에서는 다음 규칙으로 영상을 압축한다.

• 어떤 정사각형 영역의 모든 칸이 \(0\)이면 0으로 나타낸다.
• 어떤 정사각형 영역의 모든 칸이 \(1\)이면 1로 나타낸다.
• 두 경우에 모두 해당하지 않으면 영역을 크기가 같은 네 정사각형으로 나눈다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 영역을 차례대로 압축한 결과를 괄호 안에 이어 붙인다.

주어진 흑백 영상을 위 규칙으로 압축한 결과를 구하여라.

입력

첫째 줄에 영상의 한 변의 길이 \(N\)이 주어진다. \(N\)은 \(2\)의 거듭제곱이다.

다음 \(N\)개의 줄에는 영상의 각 행이 위에서부터 순서대로 주어진다. 각 줄은 공백 없이 이어진 \(N\)개의 문자 0 또는 1로 이루어진다.

출력

영상을 압축한 결과를 한 줄에 출력한다.

제한

• \(1 \le N \le 64\)
• \(N\)은 \(2\)의 거듭제곱이다.

예제 입력

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력

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