장기

차는 가로 또는 세로 방향으로 원하는 만큼 이동할 수 있는 말이다.

N x N 게임판에 차 N개를 놓으려고 한다. 단, 다음 두 조건을 모두 만족해야 한다.

1. 같은 행 또는 같은 열에 차가 두 개 이상 놓이면 안 된다.
2. 왼쪽 위에서 오른쪽 아래로 가는 대각선과 오른쪽 위에서 왼쪽 아래로 가는 대각선 위에는 차를 놓을 수 없다.

조건을 만족하는 배치가 있으면 그중 하나를 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 N(3 <= N <= 100,000)이 주어진다.

N개의 줄에 걸쳐 출력한다. i번째 줄에는 i번째 행에 놓을 차의 열 번호를 출력한다.

조건을 만족하는 배치가 여러 개라면 아무거나 출력한다. 배치가 불가능한 경우 첫째 줄에 -1만 출력한다.