Mr. Jin has a girlfriend—who has no name. She is hardworking, brave, wise, and kind. Mr. Jin likes her very much. To show his affection, Mr. Jin used $a^3$ unique $1 \times 1 \times 1$ crystal blocks to build a crystal cube with side length $a$. He wants to give this crystal cube to the most pure and kind person he has ever met.

Because the crystal cube is too large to transport, Mr. Jin decided to take it apart before sending it. He believes that assembling this crystal cube will not be difficult for her.

After receiving the gift, the girl assembled the crystal cube according to the instructions in no time. She discovered that there are $n$ crystal blocks that emit light in one of the six directions (up, down, left, right, front, back) at random during the dark and quiet night. The crystals illuminated by the light look exceptionally beautiful. The girl defined an "attractiveness value" for every crystal that does not emit light. The attractiveness of the crystal cube at night is the sum of the attractiveness values of all crystals that are illuminated by light. The girl wants to know the minimum and maximum possible attractiveness of the crystal cube at night.

Input

The first line contains $a$, representing the side length of the crystal cube.

The next $a^3$ lines each contain several integers. The first integer $g[i]$ ($g[i] \ge 0$) represents the attractiveness of the $i$-th crystal. If $g[i] = 0$, it means this crystal emits light. The following 3 to 6 integers represent the indices of the crystals that share a face with this crystal.

Output

Output a single line containing two integers: the minimum and maximum attractiveness of the crystal cube at night.

Constraints

For 100% of the data, $g[i] < 1000000$ and $a > 1$.

Examples

Input 1

2
0 7 2 3
0 8 1 4
4 5 4 1
8 6 3 2
16 3 6 7
32 4 5 8
1 1 8 5
2 2 7 6

Output 1

0 12