34881번 - 전기 회로 배치 스페셜 저지

문제

성준이는 돈을 많이 벌기 위해 알고리즘을 그만둔 후, 전기 회로 디자인을 시작했다.

전기 회로는 $N \times (N+1)$ 크기의 격자에 전기 부품을 배치함으로 만들 수 있다. $i$번째 행의 $j$번째 열을 $(i,j)$로 표현한다.

전기 회로의 $N+1$번째 열을 제외한 각 격자에는 총 3ドル$종류의 전기 부품 중 하나를 배치해야 하며 $(i,j)$에 위치한 부품은 각각 신호를 다음과 같이 전달한다.

• .: 전송받은 신호를 그대로 $(i,j+1)$에 있는 전기 부품으로 전송한다.
• a: 전송받은 신호를 그대로 $(i+1,j+1)$에 있는 전기 부품으로 전송한다.
• b: 전송받은 신호를 그대로 $(i-1,j+1)$에 있는 전기 부품으로 전송한다.

전기 회로의 $N+1$번째 열에 설치되는 전기 부품은 c 부품이며, 이 부품은 전송받은 신호를 전송하지 않고 $N+1$열 외에는 이 부품을 설치할 수 없다.

하나의 부품이 하나보다 많은 신호를 받게 되거나 전기 회로의 격자 밖으로 전기 신호를 보내게 된다면, 전기 회로는 고장 나게 된다.

전기 회로를 처음 작동시키면 $(i,1)$에 있는 전기 부품에 $i$번째 신호가 전송된다. 회로가 고장나지 않게 c부품을 제외한 전기 회로의 모든 부품이 정확히 하나의 신호를 전송한 후, $(i,N+1)$에 있는 c 부품이 $P_i$번째 신호를 전달받도록 회로를 제작한다면, 성준이는 큰 돈을 벌 수 있게 된다.

조건을 만족하며 $(i,j)$에 배치한 전기 부품을 $S_{i,j}$라고 할 때, 성준이가 큰 돈을 벌 수 있는 전기 회로 $S$를 구해보자. 만약 그러한 $S$가 여러 가지라면, 아무 $S$나 구해보자.

입력

첫째 줄에 $N$이 주어진다. (2ドル \le N \le 2,000円$)

둘째 줄에 $P_1, P_2, \ldots, P_N$이 공백으로 구분되어 주어진다. (1ドル \le P_i \le N; P_i \neq P_j$ if $i \neq j$)

출력

첫째 줄부터 $N$개의 줄에 걸쳐 $S$를 출력한다. $S$가 존재하지 않는다면 첫째 줄에 -1을 대신 출력한다.

$S$가 존재한다면 $i$번째 줄에 $S_{i,1} S_{i,2} \ldots S_{i,N}$을 공백 구분 없이 출력한다. $N$번째 열까지만 출력함에 유의하라. ($S_{i,j} \in \{$.,a,b$\}$)

만약 가능한 답이 여러 가지라면, 아무 답이나 출력한다.

제한

노트