ConanKudo và RR chơi 1 trò chơi vô cùng thú vị dành cho 2 người như sau:

• Ban đầu 2 người được cho một bảng vuông kích thước ~N \times N~, trên ô ở hàng ~i~ cột ~j~ của bảng có ghi số ~A(i,j)~.

• 2 người chơi lần lượt chơi theo lượt xen kẽ nhau. ConanKudo chơi trước. Ở mỗi lượt, một người chơi sẽ chọn 1 số nguyên dương trong khoảng ~[1,N]~ mà chưa được chọn trước đó bởi bất kỳ người chơi nào.

• Sau khi cả 2 người đã chọn hết tất cả các số nguyên dương từ ~1~ đến ~N~, điểm của 2 người chơi được tính như sau:

  • Với mỗi bộ 2 số nguyên dương ~i, j~ (~i~ có thể bằng ~j~) mà một người chơi chọn được, điểm của người chơi đó sẽ được cộng thêm ~A(i,j)~.

Đặt ~f~ = (điểm mà ConanKudo nhận được) ~-~ (điểm mà RR nhận được).

Biết rằng cả 2 người chơi đều thực hiện các nước đi một cách tối ưu, ConanKudo luôn tìm cách chơi để ~f~ đạt giá trị lớn nhất, RR luôn tìm cách chơi để ~f~ đạt giá trị nhỏ nhất. Hãy tìm các nước đi của ConanKudo.

Bài toán sẽ được chấm theo kiểu interactive: Bạn vào vai ConanKudo, và máy tính vào vai RR.

Input

Khi bắt đầu, trình chấm sẽ viết ra file input của bạn ~N+1~ dòng:

• Dòng đầu chứa số nguyên dương ~N~ ~(N \leq 100)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên dương trong khoảng ~[1,10^{6}]~ được phân cách nhau bởi ít nhất một dấu cách.

Giới hạn

Nếu tất cả các nước di chuyển bạn đưa ra đều tối ưu, bạn được trọn vẹn điểm cho test đó, nếu không, bạn không nhận được điểm nào.

Trong thời gian thi, bài của bạn chỉ được chấm với ~50\%~ số test của bài. Trong quá trình thi, điểm của bạn thể hiện phần trăm test giải đúng trong các test đó (trên thang điểm ~100~).

Sample Input

3
2 8 1
3 5 5
3 2 7

3

Sample Output

2
1

Note

Điểm của ConanKudo: ~A(2,2) + A(1,1) + A(1,2) + A(2,1) = 18~.

Điểm của RR: ~A(3,3) = 7~.

~f = 11~.

Nếu ở lượt chơi đầu tiên, ConanKudo chọn ~1~ hoặc ~3~, thì ở lượt 2, RR sẽ chọn ~2~. Khi đó, điểm của ConanKudo là ~13~, điểm của RR là ~5~, ~f = 8 < 11~.