Kim tự tháp là một trong những kỳ quan mà cho tới hiện tại, người ta vẫn không thể hiểu được những người Ai Cập cổ đại đã xây dựng nó như thế nào? Người ta mô phỏng lại cách xây kim tự tháp như sau: Có ~N~ khối đá hình hộp chữ nhật, ta xây một cái tháp bằng cách chồng các khối đá này lên nhau. Để đảm bảo an toàn, các khối đá được đặt theo nguyên tắc:

• Chiều cao của mỗi khối là kích thước nhỏ nhất trong ba kích thước.
• Các mép của các khối được đặt song song với nhau sao cho không có phần nào của khối nằm trên bị chìa ra ngoài so với khối nằm dưới.

Yêu cầu: Hãy tìm phương án xây dựng để tháp đạt được độ cao lớn nhất.

Input

• Dòng đầu tiên là số ~N~ (~N \le 5000~).
• ~N~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương (không quá 1000) là kích thước của một khối đá. Các khối đá được đánh số từ 1 theo trình tự xuất hiện trong file.

Output

• Dòng thứ nhất ghi độ cao lớn nhất của tháp xây được.
• Dòng thứ hai ghi số ~M~ là số lượng khối đá dùng để xây tháp.
• ~M~ dòng tiếp theo ghi các khối xếp từ đáy tháp lên đỉnh tháp, mỗi dòng gồm 4 số theo thứ tự ~K, a, b, c~, trong đó ~K~ là số hiệu khối đá, ~a~ là kích thước chọn làm đáy nhỏ, ~b~ là kích thước chọn làm đáy lớn, ~c~ là kích thước chọn làm chiều cao.

Sample Input 1

9 
7 5 5 
4 4 8 
1 1 5 
4 2 2 
5 1 5 
4 2 7 
2 9 2 
1 3 3 
5 5 5 

Sample Output 1

13 
4 
1 5 7 5 
9 5 5 5 
5 5 5 1 
4 2 4 2