Mốc Đủ Dữ Kiện

Có $N$ đại lượng chưa biết $x_1,x_2,\dots ,x_N$, mỗi đại lượng là một bit. $M$ phép đo được nhận theo thứ tự. Một phép đo cho biết XOR của một tập đại lượng: chuỗi nhị phân chỉ vị trí nào tham gia, còn bit cuối dòng là kết quả XOR.

Dữ liệu được bảo đảm nhất quán. Hãy tìm số phép đo ít nhất ở đầu dãy đủ để xác định duy nhất toàn bộ $N$ bit. Sau đó in giá trị của từng bit bằng các nhãn quy ước bên dưới.

Input

• Dòng đầu chứa hai số nguyên $N$ $M$.
• Dòng thứ $i$ trong $M$ dòng tiếp theo chứa một chuỗi $s_i$ độ dài $N$ và một bit $b_i$. Phép đo tương ứng là XOR của mọi $x_j$ có s_i_{j} = 1, và kết quả bằng $b_i$.

Output

• Nếu ngay cả toàn bộ $M$ phép đo vẫn không xác định duy nhất các bit, in:
• Cannot Determine

• Ngược lại, in số nguyên $K$ nhỏ nhất sao cho $K$ phép đo đầu tiên đã đủ. Sau đó in $N$ dòng theo thứ tự $x_1,\dots ,x_N$:

• in ?y7M# khi bit bằng $1$;

• in Earth khi bit bằng $0$.

Constraints

• $1\le N\le 1000$.
• $1\le M\le 2000$.
• Mỗi chuỗi có đúng $N$ ký tự $0$ hoặc $1$.
• Mỗi $b_i$ bằng $0$ hoặc $1$.
• Tất cả phép đo trong input nhất quán với ít nhất một vector bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 20,M\le 40$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3 4
110 1
011 1
101 0
001 1

4
?y7M#
Earth
?y7M#