Besi goes to work in a computer lab. She wants to determine the degree of importance of each of N lab workers (1≤N≤100). All degrees of importance are different. That is, no two employees have the same degree of importance. Besi uses the list of lab publications to determine the importance of employees.
Each publication contains a list of authors, which is an ordered list of all N employees of the laboratory. The list is compiled in descending order of the contribution of each of the employees to this article. If multiple workers have made the same contribution, then they are ordered alphabetically. Because the more important worker has additional administrative responsibilities, he never contributes more than the less important worker.
For example, if the lab consists (in ascending order of importance) of a student Elsie, prof. Mildred and prof. Dean, they can be the authors of the article (Elsie-Mildred-Dean) if they all contributed a different amount of effort. Namely, Elsie contributed more effort than Mildred, and Mildred more than Dean. However, they can also have an article in the Elsie-Dean-Mildred order if Mildred and Dean contributed the same amount of effort and Elsie is greater than both of them.
Given K publications from this lab (1≤K≤100), help Besi determine for all pairs of employees in this lab who is more important, if possible.
INPUT FORMAT
The first line contains two integers K and N.
The second line contains N lines, separated by single spaces, containing the names of the lab members. Each name consists of no more than 10 small Latin letters.
Each of the following K lines contains N lines separated by single spaces, indicating the list of authors in one publication.
OUTPUT FORMAT
The output should consist of N lines, N characters per line. On line i, for any j≠i, the j-th character must be 1 if the i-th member is more important than the j-th one, 0 if the i-th member is less important than the j-th one, and ? if it is impossible to determine given the list of publications.
The i-th character in string i should be B because that's Besi's favorite character.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
1 3
dean elsie mildred
elsie mildred dean |
B11
0b?
0?B |
In the first example, one article (elsie-mildred-dean) does not provide enough information to determine who is more important than elsie or mildred. However, Dean is definitely more important than both. Therefore both orders are possible Elsie<Mildred<Dean and Mildred<Elsie<Dean |
| 2 |
2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred |
B00
1B0
11B
| In this second example, the only possible order that satisfies both articles is Elsie<Mildred<Dean since the second posting helps determine that Mildred is more important than Elsie. |