Cho một ma trận A với kích thước N*N (2 ≤ N ≤ 1000) chỉ chứa 6 loại giá trị: {-1, -2, 0, 1, 2, 3}

A được gọi là bảng quan hệ của một dãy số T = (T₁, T₂, ..., T_n), hay T có quan hệ với A nếu:

• 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 khác T_j

Với mọi i, j: 1 <= i, j <= N

Cho bảng quan hệ A, tìm dãy số nguyên dương T = (T₁, T₂, ..., T_n) có quan hệ với A sao cho Max(T) càng nhỏ càng tốt. Cho rằng dãy số T như vậy luôn tồn tại.

Định nghĩa Max(T) = Max(T₁, T₂, ..., T_n).

Input

Dòng đầu chứa số nguyên N. N dòng tiếp theo, mỗi dòng chứa N số nguyên mô tả bảng quan hệ A.

Output

Dòng đầu chứa Max(T). Dòng thứ hai chứa N số nguyên dương 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 

-> Điểm = 4