Xây dựng bản đồ Hapmap của con người có thể giúp việc chẩn đoán bệnh cũng như tìm ra các loại thuốc chữa trị mới. Trong xây dựng bản đồ Hapmap, Haplotype và Genotype là hai khái niệm cơ bản trong sinh học được phát biểu đơn giản như sau:

1. Haplotype \(H = (h_1, \dots, h_n)\) là xâu độ dài \(n\), trong đó \(h_i\) chỉ nhận giá trị \(0\) hoặc \(1\).
2. Genotype \(G = (g_1, \dots, g_n)\) là một xâu độ dài \(N\) được tạo ra từ sự đối sánh hai Haplotype \(H = (h_1, \dots, h_n)\) và \(H' = (h_1', \dots, h_n')\) theo quy tắc sau:
   • \(g_i = 0\) nếu \(h_i = h_i' = 0\).
   • \(g_i = 1\) nếu \(h_i = h_i' = 1\).
   • \(g_i = 2\) nếu \(h_i \neq h_i'\).

Như vậy, mỗi cặp Haplotype \(H\) và \(H'\) chỉ tạo ra một Genotype \(G\) duy nhất, nhưng một Genotype \(G\) lại có thể được tạo ra từ nhiều cặp Haplotype khác nhau. Thông tin về gen của một con người được xác định bởi một cặp Haplotype. Để đáp ứng mục đích nghiên cứu, các nhà khoa học cần giải mã thông tin từ Haplotype và Genotype. Do việc giải mã là không duy nhất, nên với một tập Genotype, các nhà khoa học muốn tìm một tập gồm ít Haplotype nhất mà mỗi Genotype đều được tạo ra từ hai Haplotype trong tập.

Yêu cầu: Cho thông tin Genotype là \(G_1, \dots, G_k\) của \(k\) người, hãy tìm \(k\) cặp \((H_1, H_1'), \dots, (H_k, H_k')\) tương ứng cho \(k\) người sao cho tập \(\{H_1, H_1', \dots, H_k, H_k'\}\) có lực lượng là nhỏ nhất.

Input

• Dòng đầu ghi hai số \(k, n\) (\(k \le 100, n \le 200\)).
• Dòng thứ \(t\) (\(1 \le t \le k\)) trong \(k\) dòng tiếp theo chứa xâu độ dài \(n\) biểu diễn Genotype \(G_t\) của người thứ \(t\).

Output

• Ghi số nguyên dương \(p\) là lực lượng của các Haplotype tìm được.
• \(p\) dòng sau, mỗi dòng một xâu mô tả Haplotype.

Scoring

• Có \(10\) test, mỗi test \(10.0\) điểm. Gọi \(p\) là số Haplotype bạn tìm được, \(r\) là kết quả của Ban giám khảo, nếu \(p > 2k\) bạn sẽ bị \(0\) điểm, ngược lại bạn sẽ đạt được: \(10.0 \times \min\left\{1, \left(\frac{r}{p}\right)^3\right\}\).
• Subtask \(1\) (\(50\%\) số điểm): \(k \le 10\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

2 4
1212
1110

2
1110
1011