BOI là tên viết tắt của Baltic Olympiad in Informatics — kỳ thi Olympic Tin học Baltic.

Ban tổ chức thấy tên viết tắt BOI quá dễ phát âm, vì trong tiếng Anh nó chỉ có một âm tiết. Vì vậy, họ đã nghĩ ra một tên viết tắt mới. Để dễ phân biệt với các kỳ thi Olympic khu vực khác, chẳng hạn CEOI, tên mới vẫn chỉ gồm các ký tự B, O và I. Ngoài ra, B phải là ký tự xuất hiện nhiều nhất một cách nghiêm ngặt: số lần xuất hiện của B phải lớn hơn số lần xuất hiện của O, đồng thời lớn hơn số lần xuất hiện của I.

Ví dụ, OBOIIBB và B là những tên viết tắt hợp lệ, còn IBIIBB, BOI, O và BCB thì không.

Để mọi chuyện thú vị hơn, thay vì công bố toàn bộ tên mới, ban tổ chức chỉ đưa ra một số gợi ý. Cụ thể, với mỗi xâu con liên tiếp của tên mới, họ cho biết số lần xuất hiện của ký tự xuất hiện nhiều nhất trong xâu con đó. Ký tự này không nhất thiết là B, và có thể có nhiều ký tự cùng đạt số lần xuất hiện lớn nhất. Điều đáng ngạc nhiên là có thể chứng minh những thông tin này đủ để xác định tất cả các vị trí xuất hiện của B. Hãy tìm các vị trí đó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là độ dài của tên viết tắt mới.

\(n\) dòng tiếp theo mô tả các gợi ý. Dòng thứ \(i\) trong số này chứa \(n-i+1\) số nguyên \(M_{i,i}, M_{i,i+1}, \ldots, M_{i,n}\). Trong đó, \(M_{\ell,r}\) là số lần xuất hiện của ký tự xuất hiện nhiều nhất trong xâu con bắt đầu ở vị trí \(\ell\) và kết thúc ở vị trí \(r\). Các vị trí được đánh số từ \(1\) đến \(n\).

Dữ liệu bảo đảm tồn tại ít nhất một tên viết tắt hợp lệ phù hợp với tất cả các gợi ý.

Dữ liệu ra

In trên một dòng tất cả các vị trí xuất hiện của B theo thứ tự tăng dần, cách nhau bởi một dấu cách. Mỗi vị trí là một số nguyên từ \(1\) đến \(n\).

Ràng buộc

• \(1 \le n \le 2000\).
• \(1 \le M_{\ell,r} \le n\) với mọi \(1 \le \ell \le r \le n\).

Phân nhóm

1. \(11\) điểm: \(n \le 10\).
2. \(12\) điểm: tên viết tắt cần tìm chỉ chứa các ký tự B và O.
3. \(10\) điểm: tên viết tắt cần tìm không có hai ký tự liên tiếp giống nhau.
4. \(11\) điểm: \(n \le 40\).
5. \(19\) điểm: \(n \le 500\).
6. \(37\) điểm: không có ràng buộc bổ sung.

Ví dụ

6
1 1 2 3 3 3
1 1 2 2 2
1 2 2 2
1 1 2
1 2
1

1 3 4