THPT Chuyên Bến Tre

Một toà soạn báo Thể thao cần phân công n phóng viên (đánh số từ 1 đến n), mỗi phóng viên đến một trong số n địa điểm khác nhau (cũng được đánh số từ 1 đến n) để săn lùng tin về giải vô địch bóng đá. Mỗi phóng viên được quyền đề xuất một danh sách gồm 3 địa điểm mà họ mong muốn đến công tác xếp theo thứ tự ưa thích nhất, nhì, ba. Một cách phân công được gọi là chấp nhận được nếu như mỗi phóng viên đều được cử đến một địa điểm trong danh sách 3 địa điểm mong ước. Nếu có cách phân công chấp nhận được, toà soạn lại quan tâm tới cách phân công chấp nhận được mà trong đó số phóng viên được cử đến địa điểm mà họ ưa thích nhất là lớn nhất. Cách phân công như vậy gọi là cách phân công phù hợp.

Yêu cầu: Nếu có cách phân công chấp nhận được cần tìm cách phân công phù hợp trong đó số phóng viên được đến điểm họ ưa thích thứ nhì là nhiều nhất. Ngược lại cần đưa ra cách phân công mà trong đó số phóng viên không được đến địa điểm trong danh sách ba địa điểm họ ưa thích là nhỏ nhất.

Dữ liệu: Vào từ file văn bản ASSIGN.INP có cấu trúc như sau:

· Dòng đầu tiên chứa số nguyên dương n (n<=200)

· Dòng thứ i trong số n dòng tiếp theo chứa ba số nguyên dương ai, bi, ci là danh sách 3 địa điểm ưa thích của phóng viên i (i=1,2,...,n)

Kết quả: Ghi ra file văn bản ASSIGN.OUT theo cấu trúc sau:

· Dòng đầu tiên gho ba số p, q, r, trong đó p là số phóng viên không được đáp ứng nguyện vọng, q là số phóng viên được cử đến địa điểm ưa thích nhất, r là số phóng viên được cử đến địa điểm ưa thích thứ nhì trong cách phân công tìm được.

· Dòng thứ i trong n dòng tiếp theo ghi địa điểm mà phóng viên i dược cử đến theo cách phân công tìm được.

Example

Input:

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

Output:

0 1 1
1
2
3
4
6
5