N×N 이진 격자를 쿼드트리 방식으로 압축하라.

격자의 모든 값이 동일하면 해당 값(0 또는 1)으로 표현하고, 그렇지 않으면 4등분하여 좌상·우상·좌하·우하 순으로 재귀 압축한다.

4등분 결과는 괄호로 묶는다. 압축 결과 문자열을 출력하라.

입력

첫째 줄에는 격자의 크기 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))