Distribute the Bars

시간 제한2초메모리 제한512 MB

요약

처음 N개의 홀수를 같은 무게 합을 갖는 두 개 이상의 묶음으로 나누고, 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 수학, 그리디, 정수론
정답자: 아직 제출이 없습니다

문제

There are $N$ metal bars. The weight of $i$ -th metal bar is $2i - 1$ .

Your task is to distribute those metal bars into two or more groups such that the sum of weights of metal bars in each group will be the same, or determine that it is impossible. Note that each metal bar must go to exactly one group, and that it is not allowed to cut the metal bars.

입력

The input contains one integer $N$ ( $2 \le N \le 10^5$ ).

출력

If there is no way to distribute the metal bars into two or more equally weighted groups, print one line containing the integer $-1$ .

Otherwise, on the first line, print the number of groups $G$ ( $2 \le G \le N$ ). Then print $G$ lines, one for each group. The $i$ -th of these lines must start with the the integer $K\_i$ , the number of metal bars in the $i$ -th group. Then print $K\_i$ integers: the weights of the metal bars in the group. Each metal bar must be assigned to exactly one group, and the sums of weights of the metal bars in all groups must be the same.

If there is more than one solution, print any one of them.

예제3

예제 1
입력
```
4
```
예상 출력
```
2
2 1 7
2 3 5
```
예제 2
입력
```
2
```
예상 출력
```
-1
```
예제 3
입력
```
3
```
예상 출력
```
-1
```