Problem1550--VIJOS-P1337

1550: VIJOS-P1337

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

这个拼图游戏要求将一些图形拼成一个正方形,图形的个数从1到5。如下图所示,图形个数是4。 [img]ProblemImg/P1137_1.jpg[/img] 图形不能旋转,拼的时候不能重叠,拼完后的正方形里面不能有空隙。所有给定的图形都要使用。 [img]ProblemImg/P1137_2.jpg[/img] 左面的图表示这样拼不行,右面是一个成功的拼法。 现在,@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰;如果可以,请输出一种完成这个游戏的方案。

Input

文件的第一行是一个整数n,表示图形的个数,范围从1到5。 接下来有n个部分,每个部分的第一行是2个整数i和j,表示下面的i行j列用来描述一个图形。图形用0和1表示,1表示图形占有这个位置,0表示不占有,中间没有空格。例如上图中图形A的描述是 2  3 111 101 所有图形的长与宽都不超过5。 根据图形给出的顺序给每个图形编号,从1开始,至多到5。 保证数据无多解情况。

Output

如果不能拼成一个正方形,就输出" No  solution  possible" ;否则,输出一种拼的方案:一个正方形的数阵,每个位置上的数字是占有这个位置的图形的编号,中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4,那么就可以输出 1112 1412 3422 3442

Sample Input Copy

输入样例1:
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001

输入样例2:
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1

Sample Output Copy

输出样例1:
No solution possible

输出样例2:
1133
1153
2223
2444