Xét tập \(A\) gồm \(n\) xâu, mỗi xâu độ dài \(m\) và chỉ gồm các kí tự "0", "1" hoặc "*". Với một xâu, ta có thể biến đổi để nhận được xâu nhị phân bằng cách thay thế mỗi kí tự "*" trong xâu thành kí tự "0" hoặc "1". Biến đổi \(n\) xâu của tập \(A\) để nhận được tập xâu nhị phân \(C\) có lực lượng lớn nhất.

Yêu cầu: Cho \(n\) xâu, tìm cách biến đổi \(n\) xâu để nhận được tập xâu nhị phân \(B\) có lực lượng nhỏ nhất và tập xâu nhị phân \(C\) có lực lượng lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n, m\) (\(m \le 100\)).
• \(n\) dòng sau, mỗi dòng một xâu độ dài \(m\) chỉ gồm các kí tự "0", "1" hoặc "*" mô tả \(n\) xâu của tập \(A\).

Output

• Dòng đầu là số nguyên là lực lượng của tập \(B\), tiếp theo là \(n\) xâu nhị phân mô tả cách biến đổi từng xâu để nhận được tập \(B\), các đại lượng cách nhau đúng một dấu cách.
• Dòng thứ hai là số nguyên là lực lượng của tập \(C\), tiếp theo là \(n\) xâu nhị phân mô tả cách biến đổi từng xâu để nhận được tập \(C\), các đại lượng cách nhau đúng một dấu cách.

Scoring

• Có \(20\) test, mỗi test \(5.0\) điểm. Gọi \(s_B, s_C\) tương ứng là lực lượng của tập \(B, C\) do thí sinh tìm được và kết quả của Ban giám khảo tương ứng là \(w_B, w_C\), khi đó số điểm bạn đạt được cho mỗi test là \(2.5 \times \min\left\{1, \left(\frac{w_B}{s_B}\right)^5\right\} + 2.5 \times \min\left\{1, \left(\frac{w_C}{s_C}\right)^5\right\}\).
• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 1000\).

Example

4 3
***
01*
001
*1*

2 001 010 001 010
4 000 010 001 111