Problem C: 反对称矩阵

Problem C: 反对称矩阵

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 94  Solved: 34
[Submit] [Status] [Web Board] [Creator:]

Description

反对称矩阵是指方阵A对于任意的i≠j,满足Aij不等于Aji
现在有一个n*n的01方阵,其中还有一些空没有填,现在要求你使用0或1补全该方阵,问是否能使它成为反对称矩阵。
如果可以变为反对称矩阵,把矩阵的每行连接成一行,输出字典序最大的那个字符串,否则输出impossible。

Input

多组输入。
第一行输入矩阵的大小n(1<=n<=200)。
接下来输入一个只包含-或0或1的n*n的矩阵,
-代表为空,0和1代表已经填了的数。

Output

输出由填完矩阵得到的字典序最大的字符串。
如果填不出符合要求的矩阵,输出impossible。

Sample Input

3
1-0
--0
-1-
2
-0
0-

Sample Output

110010111
impossible

HINT

第一个用例得到的矩阵为 110
                                         010
                                         111