图形不能旋转,拼的时候不能重叠,拼完后的正方形里面不能有空隙。所有给定的图形都要使用。
左面的图表示这样拼不行,右面是一个成功的拼法。
现在,潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰;如果可以,请输出一种完成这个游戏的方案。
文件的第一行是一个整数$n$,表示图形的个数,范围从$1$到$5$。
接下来有$n$个部分,每个部分的第一行是$2$个整数$i$和$j$,表示下面的$i$行$j$列用来描述一个图形。图形用0和1表示,1表示图形占有这个位置,0表示不占有,中间没有空格。例如上图中图形$A$的描述是
2 3
111
101
所有图形的长与宽都不超过$5$。
根据图形给出的顺序给每个图形编号,从$1$开始,至多到$5$。
保证数据无多解情况。
如果不能拼成一个正方形,就输出No solution possible;否则,输出一种拼的方案:一个正方形的数阵,每个位置上的数字是占有这个位置的图形的编号,中间没有空格。例如上面$A、B、C、D$的编号依次是$1、2、3、4$,那么就可以输出
``
1112
1412
3422
3442
4 1 4 1111 1 4 1111 1 4 1111 2 3 111 001\n · \n \n · \n \n · \n \n · \n \n \n
No solution possible· · \n
样例2:
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1
1133
1153
2223
2444