Bessie đang nộp đơn vào chương trình sau đại học ngành khoa học máy tính và đã có một buổi phỏng vấn tại một phòng thí nghiệm danh tiếng. Tuy nhiên, để tránh làm phật lòng bất kỳ ai, Bessie muốn xác định thứ bậc thâm niên tương đối của \(N\) thành viên hiện tại trong phòng thí nghiệm (\(1\le N\le100\)). Không có hai thành viên nào có cùng thâm niên, nhưng việc xác định thứ bậc của họ có thể không dễ. Bessie sẽ xem các công trình công bố của phòng thí nghiệm.

Mỗi công trình có một danh sách tác giả, là một thứ tự của toàn bộ \(N\) thành viên. Danh sách được sắp theo lượng công sức mỗi thành viên đóng góp cho bài báo, từ nhiều đến ít. Nếu nhiều nhà nghiên cứu đóng góp công sức bằng nhau, họ được xếp theo thứ tự từ điển. Do các thành viên thâm niên hơn phải làm thêm các nhiệm vụ quản lý, một nhà nghiên cứu thâm niên hơn không bao giờ đóng góp nhiều công sức hơn một nhà nghiên cứu ít thâm niên hơn.

Ví dụ, xét một phòng thí nghiệm gồm sinh viên trẻ Elsie, Giáo sư Mildred thâm niên hơn và Trưởng khoa Dean rất thâm niên. Một bài báo có thể có thứ tự (Elsie-Mildred-Dean) nếu cả ba người đóng góp lượng công sức khác nhau: Elsie nhiều hơn Mildred và Mildred nhiều hơn Dean. Tuy nhiên, bài báo cũng có thể có thứ tự (Elsie-Dean-Mildred) nếu Mildred và Dean đóng góp bằng nhau, còn Elsie đóng góp nhiều hơn.

Cho \(K\) công trình của phòng thí nghiệm (\(1\le K\le100\)), hãy xác định đối với mọi cặp nhà nghiên cứu xem ai thâm niên hơn, nếu có thể suy ra được.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(K\) và \(N\).

Dòng thứ hai chứa \(N\) xâu cách nhau bởi dấu cách, là tên của các thành viên trong phòng thí nghiệm. Mỗi tên chỉ gồm các chữ cái thường và dài không quá \(10\) ký tự.

Mỗi dòng trong \(K\) dòng tiếp theo chứa \(N\) xâu cách nhau bởi dấu cách, biểu diễn danh sách tác giả của một công trình.

Dữ liệu ra

In \(N\) dòng, mỗi dòng gồm \(N\) ký tự. Trên dòng \(i\), với mọi \(j\ne i\), ký tự thứ \(j\) phải là:

• \(1\) nếu chắc chắn thành viên thứ \(i\) thâm niên hơn thành viên thứ \(j\);
• \(0\) nếu chắc chắn thành viên thứ \(i\) ít thâm niên hơn thành viên thứ \(j\);
• \(?\) nếu không thể suy ra từ các công trình đã cho.

Ký tự thứ \(i\) trên dòng \(i\) phải là \(B\), vì đó là chữ cái Bessie yêu thích.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

1 3
dean elsie mildred
elsie mildred dean

B11
0B?
0?B

2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred

B00
1B0
11B

Giải thích ví dụ 1. Bài báo duy nhất (elsie-mildred-dean) không cung cấp đủ thông tin để xác định Elsie hay Mildred thâm niên hơn. Tuy nhiên, có thể suy ra Dean phải thâm niên hơn cả hai, nên hai thứ tự thâm niên Elsie<Mildred<Dean và Mildred<Elsie<Dean đều có thể xảy ra.

Giải thích ví dụ 2. Thứ tự thâm niên duy nhất phù hợp với cả hai bài báo là Elsie<Mildred<Dean. Bài báo thứ hai bổ sung thông tin từ ví dụ thứ nhất và giúp suy ra Mildred cũng thâm niên hơn Elsie.

Nguồn

USACO 2021 US Open, Bronze - Acowdemia II: https://usaco.org/index.php?page=viewproblem2&cpid=1132

Tác giả: Dhruv Rohatgi.