34516번 - T 타일링 스페셜 저지

테트리스 게임에 막 입문한 유틸은 T 스핀 기술을 연습하고 있었다. 여러 번 T 모양 블록을 돌려 맞추다 보니, 문득 이런 생각이 들었다.

"T 블록만으로 커다란 격자판을 빈칸 없이 채울 수 있을까?"

그래서 유틸은 실제 게임처럼 블록을 쌓는 대신, 순수하게 T 모양 타일만으로 $N \times N$ 크기의 정사각 격자판을 빈칸 없이 채워보기로 했다.

T 타일은 아래 그림과 같이 T 모양을 기본으로 하며, 시계 방향으로 $0^\circ$, $90^\circ$, $180^\circ$, $270^\circ$ 회전하여 사용할 수 있다.

T 타일은 겹치거나 격자판 밖으로 나가면 안 된다. T 타일을 이용해 격자판을 빈칸 없이 채우는 방법을 구해보자.

첫 번째 줄에 정수 $N$이 주어진다.

격자판을 빈칸 없이 채우는 것이 가능하다면, $N$개의 줄에 걸쳐 격자판의 배치를 다음과 같이 출력한다.

• 각 줄에는 길이 $N$의 문자열을 출력한다. 출력할 수 있는 문자는 다음과 같다.
  • a: 타일이 시계 방향으로 $0^\circ$ 회전 상태인 칸
  • b: 타일이 시계 방향으로 $90^\circ$ 회전 상태인 칸
  • c: 타일이 시계 방향으로 $180^\circ$ 회전 상태인 칸
  • d: 타일이 시계 방향으로 $270^\circ$ 회전 상태인 칸

격자판을 빈칸 없이 채우는 것이 불가능하다면 첫 번째 줄에 -1을 출력한다.

• $3 \le N \le 200$