Nhân dịp sang năm mới, một chương trình xổ số được tổ chức với quy mô giải thưởng lên tới hàng tỷ đồng. Đây là cơ hội đổi đời của mỗi người và cũng chính là một cơ hội to lớn của bạn. Cách thức tham gia rất đơn giản, bạn chỉ mua các tờ vé số và nhận phần thưởng với những tấm vé số trúng giải. Đơn vị tổ chức đã bắt đầu mở bán vé số ở các đại lý trên toàn quốc. Mỗi tờ vé số sẽ có một dãy số gồm \(n\) số nguyên dương \(a_1, a_2,\ldots, a_n\) là một dãy hoán vị từ \(1\) đến \(n\). Một điều chưa từng có trong tiền lệ đó là: Đơn vị tổ chức sẽ cung cấp gợi ý về những tấm vé số đạt giải. Gợi ý là một mã QR có dạng một ma trận nhị phân kích thước \(n \times n\), ô ở hàng thứ \(i\) và cột thứ \(j\) có số \(b_{i,j}\).

Thông tin được cung cấp thêm như sau: Trên mỗi dãy hoán vị, một thao tác thay đổi được thực hiện bằng cách chọn một chỉ số \(i\) (\(1<i<n\)) và gán \(a_i\) bằng trung vị của dãy \(\{a_{i-1}, a_i, a_{i+1}\}\). Trên ma trận gợi ý, giá trị \(b_{i,j} = 1\) nếu có thể tạo ra \(a_i = j\) sau một số thao tác thay đổi, ngược lại giá trị \(b_{i,j} = 0\). Những tấm vé số đạt giải nếu có dãy hoán vị thỏa mãn ma trận gợi ý mà đơn vị tổ chức cung cấp.

Nhắc lại, trung vị của một dãy là phần tử ở giữa sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy \(\{5, 2, 3\}\) là \(3\).

Từ những thông tin gợi ý cung cấp, hãy tìm ra một tấm vé số đạt giải và đi lĩnh thưởng.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 5000\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa chứa \(n\) số nguyên \(b_{i,1}, b_{i,2},\ldots, b_{i,n}\) (\(0 \leq b_{i,j} \leq 1\)) mô tả hàng thứ \(i\) của ma trận gợi ý.

Output

• In ra một dãy hoán vị từ \(1\) đến \(n\) thỏa mãn ma trận gợi ý. Nếu có nhiều đáp án thỏa mãn, chỉ cần in ra một đáp án bất kỳ.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 50\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 400\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
10000
00111
00110
00110
01000

1 5 3 4 2