Khuôn viên của trường đại học có hình vuông, được chia thành ~n \times n~ ô. Ở mỗi ô có một tòa nhà, 2 tòa nhà ở cặp ô kề cạnh được nối với nhau bằng hành lang có mái che. Để tạo điều kiện cho sinh viên có nhiều thời gian học tập và nghiên cứu khoa học tại mỗi ô có lắp một máy bán thức ăn tự động, mỗi máy chỉ bán một loại đồ ăn ví dụ chỉ bán cà phê hay chỉ bán bánh mỳ kẹp thịt. Ký túc xá ở ô ~(1, 1)~ – ô ở góc trên trái. Giảng đường ở ô ~(n, n)~ tại góc dưới phải. Sinh viên luôn đi từ ký túc xá tới giảng đường theo đường đi ngắn nhất. Người ta nhận thấy sinh viên hay mua đồ ăn nhất khi đi lên lớp hoặc khi từ trên lớp về ký túc xá, vì vậy cần xem lại hệ thống đặt máy tự động sao cho trên đường đi số thức ăn có thể mua càng đa dạng càng tốt. Máy ở ô ~(i, j)~ bán thức ăn loại ~a_{ij}~. Số lượng máy cùng bán loại thức ăn này trên đường đi ngắn nhất từ ký túc xá đến giảng đường đi qua ô ~(i, j)~ và chứa nhiều máy nhất cùng bán thức ăn ~a_{ij}~ được gọi là độ lặp của máy tự động ở ô ~(i, j)~.

Yêu cầu: Hãy xác định với mỗi giá trị ~k~ trong phạm vi từ 1 đến ~2 \times n - 1~ có bao nhiêu máy tự động có độ lặp ~k~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~2 \le n \le 1500~).
• Dòng thứ ~i~ trong ~n~ dòng sau chứa ~n~ số nguyên ~a_{i1}, a_{i2}, \dots, a_{in}~ (~1 \le a_{ij} \le n^2~).

Output

• Đưa ra trên một dòng ~2 \times n - 1~ số nguyên – các giá trị tìm được.

Sample Input 1

5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1

Sample Output 1

2 4 9 0 0 1 1 8 0