Brotherly Field Division

There is a rice field made of N x N unit plots. Each plot has a predicted rice harvest, measured in sacks.

Two brothers will divide the field by columns. In each column, the elder brother receives some number of plots from the bottom, and the younger brother receives the remaining plots above them. Let h_i be the number of plots given to the elder brother in column i. The division must form a staircase, so it must satisfy 0 <= h_1 <= h_2 <= ... <= h_N <= N.

Divide the field so that the absolute difference between the brothers' predicted harvest totals is as small as possible. Find that minimum difference and one corresponding sequence h_1, h_2, ..., h_N.

The first line contains the field size N (2 <= N <= 20).

Each of the next N lines describes one row of the field, from the top row to the bottom row. Each row contains N integers between 0 and 100, separated by spaces.

On the first line, print the minimum possible difference between the two predicted harvest totals.

On the second line, print N integers: the values h_1, h_2, ..., h_N from the first column through the N-th column. If there are several optimal divisions, print any one of them.