Given a matrix A with dimension N*N (2 ≤ N ≤ 1000) which contains only 6 types of value: {-1, -2, 0, 1, 2, 3}

A is called the relative board of a sequence T = (T₁, T₂, ..., T_n), or T relates to A if:

• A_ij = 0 : T_i = T_j
• A_ij = 1 : T_i < T_j
• A_ij = -1 : T_i > T_j
• A_ij = 2 : T_i ≤ T_j
• A_ij = -2 : T_i ≥ T_j
• A_ij = 3 : T_i is not equal to T_j

For all i, j: 1 <= i, j <= N

Given the relative board A, find the sequence of positive integers T = (T₁, T₂, ..., T_n) that relates to A such that Max(T) is as small as possible. Suppose that the sequence T always exists.

Define Max(T) = Max(T₁, T₂, ..., T_n).

Input

The first line contains an integer N. N lines follow, each line contains N integers that describe the relative board A.

Output

The first line contains Max(T). The second line contains N separated positive integers T₁, T₂, .., T_n.

Score

Example

Input:
6
 0  1  1  1  2  2
-2  0  1  0  2  2
-2 -1  0  3  0  1
-2 -2  3  0  1  1
-1 -2  0 -1  0  1
-1 -2 -1 -1 -1  0

Output:
4
1 2 3 2 3 4 

-> Score = 4