종이 자르기

송유진은 L x L 크기의 정사각형 모눈종이를 가지고 있다. 이 모눈종이는 가로 L칸, 세로 L칸으로 나뉘며, 각 칸은 1 x 1 크기의 정사각형이다.

차영훈은 이 모눈종이를 격자선을 따라 잘라 정확히 5개의 조각으로 만들었다. 이제 송유진은 주어진 다섯 조각을 회전하지 않고 L x L 정사각형 안에 다시 배치해야 한다.

첫째 줄에 정사각형 한 변의 길이 L이 주어진다. (3 <= L <= 10)

그다음에는 첫 번째 조각부터 다섯 번째 조각까지의 정보가 차례대로 주어진다.

각 조각의 정보는 다음 형식이다.

• 첫째 줄에 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 <= N, M <= L)
• 이어지는 N개의 줄에는 조각의 모양이 주어진다. 각 줄은 길이 M이며 #과 .으로만 이루어져 있다.
• #은 조각이 차지하는 칸, .은 빈칸을 뜻한다.
• 조각 정보의 첫 행, 마지막 행, 첫 열, 마지막 열에는 각각 적어도 하나의 #이 있다.

다섯 조각을 회전하지 않고 L x L 정사각형에 겹치지 않게 배치하여 모든 칸을 채울 수 있다면, 각 칸을 차지한 조각의 번호를 출력한다. 조각 번호는 입력으로 주어진 순서대로 1부터 5까지이다.

출력은 L개의 줄로 이루어지며, 각 줄은 해당 행의 L개 칸에 적힌 번호를 나타낸다.

가능한 배치가 여러 가지라면, 모든 행을 위에서부터 차례대로 이어 붙여 만든 문자열이 사전순으로 가장 앞서는 배치를 출력한다.

조건을 만족하는 배치가 없으면 gg를 출력한다.