시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 2 2 100.000%

문제

크기가 n이고, 체커보드처럼 n×n개의 칸으로 나누어져 있는 정사각형이 있다. 1 ≤ x1, y1, x2, y2 ≤ n 을 만족하는 두 위치 (x1, y1)와 (x2, y2)가 독립이 되려면, 서로 다른 행과 열을 차지하고 있어야 한다. 즉, x1 ≠ x2, y1 ≠ y2가 되어야 한다.n개의 위치가 독립일 되려면, 모든 쌍이 독립이 되어야 한다. 즉, 서로 다른 n개의 위치를 독립이 되도록 고르는 방법의 수는 총 n!개이다.

정사각형의 각 칸에 숫자가 써있다. 이 정사각형이 동차 정사각형이 되려면, n개의 독립적인 위치에 써 있는 숫자의 합이 고르는 방법과 상관없이 항상 같아야 한다.

정사각형에 써 있는 숫자가 주어졌을 때, 동차 정사각형인지 아닌지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 정사각형의 크기 n이 주어진다. (1 ≤ n ≤ 1000) 다음 n개 줄에는 n개의 숫자가 공백으로 구분되어서 주어진다. 각 숫자는 [-1000000, 1000000] 범위 내에 들어있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 동차 정사각형이라면 "homogeneous"를, 아니라면 "not homogeneous"를 출력한다.

예제 입력

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

예제 출력

homogeneous
not homogeneous

힌트