Có \(n\) khối đá hình hộp chữ nhật. Người ta muốn 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 cạnh đáy 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 (tức là nếu khối trên có kích thước đáy là \((a_1, b_1)\) và khối dưới có kích thước đáy là \((a_2, b_2)\) với \(a \le b\) thì phải thỏa mãn \(a_1 \le a_2\) và \(b_1 \le b_2\)).

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 chứa số nguyên \(n\).
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên dương 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 tệp.

Output

• Dòng \(1\): ghi số \(s\) là độ cao tháp đạt được.
• Dòng \(2\): ghi số \(m\) là số lượng khối đá dùng để xây tháp.
• \(m\) dòng tiếp theo ghi thông tin các khối đá xếp từ đáy tháp lên đến đỉnh tháp, mỗi dòng chứa \(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.

(Nếu chỉ đúng giá trị \(s\) ở dòng \(1\) thì được \(50\%\) số điểm của test)

Example

6
7 5 5
4 4 8
4 2 2
5 1 5
4 2 7
5 5 5

13
4
1 5 7 5
6 5 5 5
4 5 5 1
3 2 4 2

Constraints

• Các số trong dữ liệu vào đều nguyên dương.
• \(n \le 10^4\).
• Các kích thước của các khối đá không quá \(255\).
• Các số trên cùng một dòng trong các tệp dữ liệu cách nhau ít nhất một dấu cách.

Scoring

• Có \(25\%\) số điểm tương ứng với test của bài thỏa mãn điều kiện: các khối đá đều có kích thước \(a = b = c\).
• Có \(25\%\) số điểm khác tương ứng với test của bài thỏa mãn điều kiện: các khối đá đều có \(2\) trong \(3\) kích thước là \(1\).
• Có \(50\%\) số điểm còn lại tương ứng với test không có ràng buộc gì thêm.