시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)167605541.667%

문제

볼록 격자 $N$각형이란, $N$개의 점으로 이루어진 모든 점의 좌표가 정수인 볼록 $N$각형을 의미한다. 여기서 어떤 다각형이 볼록하다는 것은, 모든 내각이 $180^\circ$ 미만이며, 다각형을 이루는 임의의 변을 연장해도 그 다각형의 내부를 지나지 않음을 의미한다.

볼록 격자 $N$각형의 $N$개의 점들 중 $2$개의 점을 골라 만들 수 있는 선분의 개수는 $M=\binom{N}{2}$개, $3$개 이상의 점을 골라 만들 수 있는 볼록 다각형의 수는 $K=\binom{N}{3} +\binom{N}{4} +\binom{N}{5} +\cdots =2^N-\binom{N}{0} -\binom{N}{1} -\binom{N}{2}$개가 존재한다.

이때, $M$개의 선분의 길이는 모두 무리수이며, $K$개의 볼록 다각형의 넓이는 모두 유리수가 되도록 하는 볼록 격자 $N$각형을 실수로 만든 유리라 부르기로 했다.

$N$이 주어졌을 때, $N$개의 점으로 이루어진 실수로 만든 유리가 있다면 찾아보자.

입력

첫 번째 줄에 정수 $N(1\le N\le 10^4)$이 주어진다.

출력

첫 번째 줄부터 $N$개의 줄에 걸쳐 $N$개의 점으로 이루어진 실수로 만든 유리를 구성하는 점의 좌표 $\left( x,y \right)$을 출력한다. 각 좌표의 범위는 $0\le x,y\le 5\times 10^7$을 만족해야 한다.

만약 주어진 범위 내의 정답이 존재하지 않는다면 대신 첫 번째 줄에 -1을 출력한다.

서브태스크

번호배점제한
110

$N\le 2$

230

$N\le 5\,000$

360

추가적인 제한 조건 없음

예제 입력 1

2

예제 출력 1

-1

$2$개의 점으로 이루어진 볼록 다각형은 존재하지 않으므로, $2$개의 점으로 이루어진 실수로 만든 유리는 존재하지 않는다.

예제 입력 2

4

예제 출력 2

124124 0
690690 814814
814814 124124
0 690690

예제에서 만든 사각형은 아래와 같이 정사각형이고, $6$개의 선분의 길이는 네 개의 $2\, 002\sqrt{122\, 869}$, 두 개의 $2\, 002\sqrt{245\, 738}$으로 모두 무리수이며, $5$개의 볼록 다각형의 넓이는 네 개의 $246\, 229\, 721\, 738$, 한 개의 $492\, 459\, 443\, 476$로 모두 유리수이다.

볼록 다각형을 순서대로 출력하지 않아도 됨에 유의하자.

채점 및 기타 정보

  • 예제는 채점하지 않는다.