33930번 - 삼각형 수열 스페셜 저지

문제

당신에게는 1ドル$부터 $N$까지의 정수가 있으며, 각 수 $i$는 $i$개씩 존재한다. 예를 들어 $N=4$일 때, 1ドル$이 1ドル$개, 2ドル$가 2ドル$개, 3ドル$이 3ドル$개, 4ドル$가 4ドル$개 있다. 당신은 이 수들을 아래 그림과 같이 삼각형 모양으로 배치하려고 한다.

$i$행의 $j$번째 수를 $(i,j)$로 표현했을 때, $(i,j)$는 아래와 같은 조건에 의해 최대 6ドル$개의 다른 수와 인접해 있다.

• $i\ge 2$ 이고 $j\ge 2$ 라면, $(i-1,j-1)$와 인접해 있다.
• $i\ge 2$ 이고 $j\le i-1$ 라면, $(i-1,j)$와 인접해 있다.
• $j\ge 2$ 라면, $(i,j-1)$와 인접해 있다.
• $j\le i-1$ 라면, $(i,j+1)$와 인접해 있다.
• $i\le N-1$ 라면, $(i+1,j),ドル $(i+1,j+1)$와 인접해 있다.

이때 모든 수들에 대해서, 수에 인접해 있는 최대 6ドル$개의 수가 해당 수와 같지 않다면 이를 올바른 삼각형 수열이라고 한다. 인접한 수가 없을 경우, 해당 수는 자신과 같은 수가 인접하지 않다는 조건을 만족한 것으로 본다.

아래 그림에서, 왼쪽의 배치는 이를 만족하지 못하므로 올바른 삼각형 수열이 아니다. 반면, 오른쪽의 배치는 이를 만족하므로 올바른 삼각형 수열이 된다.

$N$이 주어졌을 때, 올바른 삼각형 수열을 출력하라. 답이 여러 개 존재한다면 그중 아무거나 하나를 출력하라. 만약 그런 배치가 존재하지 않는다면 -1을 출력하라.

입력

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

출력

$N$개의 줄에 삼각형 수열을 이루는 수들을 공백으로 구분해 출력한다. $i$번째 줄에는 그 줄에 속하는 $i$개의 수들을 왼쪽부터 순서대로 출력한다.

만약 그런 배치가 존재하지 않는다면 대신 첫 번째 줄에 -1을 출력한다.

제한

• 1ドル\le N\le 1,円 000$
• 1ドル\le i\le N$

힌트