Anti-Fan Death

시간 제한1초메모리 제한1024 MB

요약
3N x 3N 격자에 A, N, Z를 각 행과 열마다 N개씩 배치하면서 오른쪽, 아래, 오른쪽 아래 방향 어디에도 연속된 ANZ가 나타나지 않게 채우는 문제다.
난이도

보통10점 중 7점

유형
그리디, 구현, 수학
정답자
아직 제출이 없습니다

문제

SUAPC 사무실에는 3N×3N3N \times 3N 크기의 격자로 이루어져 있는 거대한 창문이 있다. 2025년 새해를 맞아 ANZ는 이 창문을 자신의 닉네임을 이루는 알파벳 3개 A, N, Z를 사용하여 창문을 꾸미고자 한다. ANZ는 창문이 다채로워 보이길 바라기 때문에, 다음 조건을 만족하도록 꾸미려고 한다.

  • 창문을 이루는 각 격자 칸에는 하나의 알파벳만을 사용할 수 있다.
  • 창문의 모든 행과 열에 알파벳 A, N, Z가 각각 정확히 NN개씩 포함되어야 한다.

하지만 ANZ는 직접 창문을 꾸미기가 너무나도 귀찮아진 나머지 plast에게 이 일을 대신 맡기고 낮잠을 자러 갔다.

일을 떠맡게 된 plast는 ANZ의 안티팬이 되기로 결심했다. 그래서 창문을 조건에 맞춰 꾸미되 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 연속된 세 글자에서 닉네임 “ANZ”가 나타나지 않도록 꾸미기로 했다. 즉, W_i,jW\_{i,j}가 창문의 ii행 jj열에 쓰인 알파벳일 때 다음 세 칸에 적힌 알파벳을 연속으로 읽어도 “ANZ”가 나타나지 않아야 한다.

  • 오른쪽: W_i,j,W_i,j+1,W_i,j+2W\_{i, j}, W\_{i, j+1}, W\_{i, j+2} (1≤i≤3N;(1 \le i \le 3N; 1≤j≤3N−2)1 \le j \le 3N-2)
  • 아래쪽: W_i,j,W_i+1,j,W_i+2,jW\_{i, j}, W\_{i+1, j}, W\_{i+2, j} (1≤i≤3N−2;(1 \le i \le 3N-2; 1≤j≤3N)1 \le j \le 3N)
  • 오른쪽 아래 대각선: W_i,j,W_i+1,j+1,W_i+2,j+2W\_{i, j}, W\_{i+1, j+1}, W\_{i+2, j+2} (1≤i≤3N−2(1 \le i \le 3N-2; 1≤j≤3N−2)1 \le j \le 3N-2)

plast가 꾸민 창문이 어떤 모양인지 알아내 보자.

입력

첫 번째 줄에 각 행과 열에 포함되어야 하는 각 알파벳(A, N, Z)의 개수 NN이 주어진다. (1≤N≤100)(1 \le N \le 100)

출력

3N3N개의 줄에 걸쳐, plast가 꾸민 창문을 출력하시오. ii번째 줄의 jj번째 문자는 창문의 ii행 jj열에 사용한 알파벳이어야 한다.

만약 문제의 조건에 맞게 창문을 꾸미는 방법이 존재하지 않는다면, -1을 출력하시오.

예제1

  1. 예제 1

    입력
    2
    
    예상 출력
    ZAZNAN
    NZNAZA
    NZNAZA
    ANAZNZ
    ZAZNAN
    ANAZNZ