Under construction

Still being built. Things may change

Number of Papers

Time limit2sMemory limit256 MB

Summary
Given an N x N grid of -1, 0, 1 values, recursively split non-uniform blocks into 9 equal sub-squares and count how many final uniform blocks hold each value.
Level

Medium5 of 10

Topics
Divide and conquer, Recursion, Matrix, Implementation
Solved
No attempts yet

Problem

You are given an N×N square paper represented as a matrix. Each cell contains one of the numbers -1, 0, and 1.

Cut the paper by the following rules.

  1. If every cell in the current paper contains the same number, use that paper as it is and do not cut it further.
  2. Otherwise, divide the current paper into 9 equal square pieces, and repeat the same process for each piece.

After all cutting is complete, find the number of papers made only of -1, the number of papers made only of 0, and the number of papers made only of 1.

Input

The first line contains N. N is at least 1, at most 3^7, and is a power of 3.

The next N lines contain the matrix representing the paper. Each line contains N integers separated by spaces, and each integer is one of -1, 0, and 1.

Output

On the first line, print the number of papers made only of -1.

On the second line, print the number of papers made only of 0.

On the third line, print the number of papers made only of 1.

Examples1

  1. Example 1

    Input
    9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1
    Expected output
    10
12
11