주어진 땅을 일정한 규칙에 따라 나누어 다양한 크기를 가진 정사각형 모양의 영역으로 구분하려고 한다.

땅의 각 칸에는 그 칸의 가치를 나타내는 정수가 하나씩 적혀 있으며, 가치는 음수일 수도 있다.

전체 영역의 크기는 \(n \times n\) (\(n = 2^k\), \(k\)는 \(1\) 이상 \(7\) 이하의 자연수)이다.

전체 영역을 가로와 세로로 분리하여 똑같은 크기의 \(4\)개의 \(\frac{n}{2} \times \frac{n}{2}\) 영역으로 나눈다.

나누어진 영역도 같은 방법으로 똑같은 크기의 네 개의 영역으로 나눈다. 이와 같은 과정을 영역이 하나의 정사각형 칸이 되어 더 이상 나눌 수 없을 때까지 반복한다.

이렇게 하면 한 변의 길이가 \(1, 2, 4, \dots, n\)인 영역들이 만들어진다. 영역의 가치는 그 영역에 속한 모든 칸에 적힌 수의 합이다.

각 크기별로, 그 크기의 영역들의 가치 중 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 영역의 한 변의 길이 \(n\)이 주어진다. \(n\)은 \(2, 4, 8, 16, 32, 64, 128\) 중 하나이다.

영역의 각 가로줄의 칸들에 적힌 수가 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

한 변의 길이가 \(1\)인 영역부터 \(2, 4, \dots\) 순서로 한 변의 길이가 \(n\)인 영역까지, 각 크기의 영역들의 가치 중 최댓값을 한 줄에 하나씩 출력한다.

제한 사항

• \(n = 2^k\) (\(1 \le k \le 7\))
• 각 칸에 적힌 수는 \(-100\) 이상 \(100\) 이하의 정수이다.

예제 입력 1

4
3 -2 5 1
0 4 -7 2
-1 -1 6 8
-3 2 0 9

예제 출력 1

9
23
26

예제 입력 2

2
-5 -1
-2 -8

예제 출력 2

-1
-16

노트

예제 1에서 한 변의 길이가 \(2\)인 영역은 다음 \(4\)개이다.

• 왼쪽 위: \(3 + (-2) + 0 + 4 = 5\)
• 오른쪽 위: \(5 + 1 + (-7) + 2 = 1\)
• 왼쪽 아래: \((-1) + (-1) + (-3) + 2 = -3\)
• 오른쪽 아래: \(6 + 8 + 0 + 9 = 23\)

따라서 한 변의 길이가 \(2\)인 영역의 가치 중 최댓값은 \(23\)이다. 한 변의 길이가 \(1\)인 영역의 가치는 각 칸의 수이므로 최댓값은 \(9\)이고, 한 변의 길이가 \(4\)인 영역은 전체 영역 하나뿐이므로 최댓값은 \(26\)이다.

예제 2처럼 모든 수가 음수이면 최댓값도 음수가 된다.