T 타일링
time limit per test
1 secondmemory limit per test
1024 megabytesinput
standard inputoutput
standard output$$$N \times N$$$ 크기의 정사각형 격자판이 주어진다. 이 격자판을 T-테트로미노 타일로 빈칸 없이 채우려고 한다. T 타일은 아래 그림과 같이 T 모양을 기본으로 하며, 시계 방향으로 $$$0^\circ$$$, $$$90^\circ$$$, $$$180^\circ$$$, $$$270^\circ$$$ 회전하여 사용할 수 있다.
T 타일은 겹치거나 격자판 밖으로 나가면 안 된다. T 타일을 이용해 격자판을 빈칸 없이 채우는 방법을 구해보자.
Input
첫 번째 줄에 정수 $$$N$$$이 주어진다.
Output
격자판을 빈칸 없이 채우는 것이 가능하다면, $$$N$$$개의 줄에 걸쳐 격자판의 배치를 다음과 같이 출력한다.
- 각 줄에는 길이 $$$N$$$의 문자열을 출력한다. 출력할 수 있는 문자는 다음과 같다.
- a : 타일이 시계 방향으로 $$$0^\circ$$$ 회전 상태인 칸
- b : 타일이 시계 방향으로 $$$90^\circ$$$ 회전 상태인 칸
- c : 타일이 시계 방향으로 $$$180^\circ$$$ 회전 상태인 칸
- d : 타일이 시계 방향으로 $$$270^\circ$$$ 회전 상태인 칸
격자판을 빈칸 없이 채우는 것이 불가능하다면 첫 번째 줄에 -1을 출력한다.
Examples
Input
8
Output
aaacaaab dacccabb ddcaaacb dcccaccc daaacaaa ddacccab dcaaacbb cccacccb
Input
3
Output
-1
Note
- $$$3 \le N \le 200$$$