Lễ hội "Hoa Đăng" tại công viên Năng Khiếu được tổ chức trong một khuôn viên có bản đồ là lưới ô vuông đơn vị kích thước ~m×n~, trên đó có một số ô đánh dấu cần mắc đèn. Ban tổ chức muốn trang trí khuôn viên này bằng các đèn màu mắc tại các ô đã đánh dấu, mỗi ô một đèn, sao cho trên mỗi hàng và mỗi cột tất cả các đèn đều có màu khác nhau và số màu phải dùng là ít nhất có thể. (Màu của các đèn được mã hóa bởi các số nguyên dương được đánh số từ 1).
*  *  *    1 2 3
*  *  *    3 1 2
*  *  _    2 3

Yêu cầu:

Thực hiện yêu cầu của BTC.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương m, n.
• Các dòng tiếp theo ghi chỉ số vị trí cần mắc đèn.

Kết quả:

• Dòng 1: Ghi số màu cần sử dụng k.
• Các dòng tiếp, mỗi dòng ghi chỉ số hàng, chỉ số cột của một ô đã đánh dấu và màu của đèn mắc tại ô đó

Giới hạn:

~n, m≤200.~

Input

3 3
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

Output

3
1 1 1
1 2 2
1 3 3
2 1 3
2 2 1
2 3 2
3 1 2
3 2 3