Paper Folding

Interview

Time limit1sMemory limit512 MB

Summary

Given an N by N grid of numbers (N is a power of two), fold the paper in half repeatedly adding overlapping cells until one number remains; print it.

Level: Easy3 of 10
Topics: Array, Math, Implementation
Solved: No attempts yet

Problem

Juseong, who likes both paper folding and math, found a game that combines the two. He writes a number in each cell of an $N \times N$ sheet of colored paper, then folds the paper in half repeatedly, adding the numbers in the cells that overlap each time. He repeats this until the paper can no longer be folded, and finds the single number that remains at the end.

The figures below show this game in detail on a 2×2 sheet.

Fold the paper exactly in half from left to right.
Add the numbers in each pair of overlapping cells. In the figure, (1, 1) and (1, 2) overlap, and (2, 1) and (2, 2) overlap.
Write each sum back onto the paper.

Fold the paper exactly in half from bottom to top.
Add the numbers in each pair of overlapping cells. In the figure, (1, 1) and (2, 1) overlap.
Write each sum back onto the paper.

Ignore the paper getting thicker as it is folded. Repeat the process above until the paper can no longer be folded, and find the number that remains at the end.

Input

The first line gives the integer $N$ , the width and height of the paper. ( $N = 2^m$ , $1 \le m \le 10$ )

From the second line to the last line, the $N \times N$ paper is given. Each cell contains an integer $K$ . ( $1 \le K \le 100{,}000$ )

Output

Print the number that remains after repeatedly folding the paper in half and adding the numbers in the overlapping cells.

Examples1

Example 1
Input
```
4
2 6 5 4
1 5 7 6
9 8 8 7
1 4 7 8
```
Expected output
```
88
```