Anti-Fan Death
시간 제한1초메모리 제한1024 MB
3N x 3N 격자에 A, N, Z를 각 행과 열마다 N개씩 배치하면서 오른쪽, 아래, 오른쪽 아래 방향 어디에도 연속된 ANZ가 나타나지 않게 채우는 문제다.
문제
SUAPC 사무실에는 크기의 격자로 이루어져 있는 거대한 창문이 있다. 2025년 새해를 맞아 ANZ는 이 창문을 자신의 닉네임을 이루는 알파벳 3개 A, N, Z를 사용하여 창문을 꾸미고자 한다. ANZ는 창문이 다채로워 보이길 바라기 때문에, 다음 조건을 만족하도록 꾸미려고 한다.
- 창문을 이루는 각 격자 칸에는 하나의 알파벳만을 사용할 수 있다.
- 창문의 모든 행과 열에 알파벳
A,N,Z가 각각 정확히 개씩 포함되어야 한다.
하지만 ANZ는 직접 창문을 꾸미기가 너무나도 귀찮아진 나머지 plast에게 이 일을 대신 맡기고 낮잠을 자러 갔다.
일을 떠맡게 된 plast는 ANZ의 안티팬이 되기로 결심했다. 그래서 창문을 조건에 맞춰 꾸미되 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 연속된 세 글자에서 닉네임 “ANZ”가 나타나지 않도록 꾸미기로 했다. 즉, 가 창문의 행 열에 쓰인 알파벳일 때 다음 세 칸에 적힌 알파벳을 연속으로 읽어도 “ANZ”가 나타나지 않아야 한다.
- 오른쪽:
- 아래쪽:
- 오른쪽 아래 대각선: ;
plast가 꾸민 창문이 어떤 모양인지 알아내 보자.
입력
첫 번째 줄에 각 행과 열에 포함되어야 하는 각 알파벳(A, N, Z)의 개수 이 주어진다.
출력
개의 줄에 걸쳐, plast가 꾸민 창문을 출력하시오. 번째 줄의 번째 문자는 창문의 행 열에 사용한 알파벳이어야 한다.
만약 문제의 조건에 맞게 창문을 꾸미는 방법이 존재하지 않는다면, -1을 출력하시오.