선물

면접 대비

시간 제한5초메모리 제한1024 MB

요약

번호가 1부터 N까지인 사탕 봉지를 아이들이 모두 같은 개수씩 받도록 나눌 때, 가장 많은 아이에게 나눠 주는 방법을 구합니다.

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

문제

Bajtosia와 Bajtek은 성 니콜라스 축일에 학교 학생들에게 줄 선물을 준비하고 있다. 둘은 가장 좋은 선물이 사탕을 많이 주는 것이라고 뜻을 모았다(이에는 좋지 않을 수 있지만). Bajtek은 사탕이 든 포장 $N$ 개를 샀다. 포장 $i$ 에는 사탕이 $i$ 개 들어 있으며, $i = 1, 2, \ldots, N$ 이다.

Bajtosia는 모든 사탕을 가능한 한 많은 아이에게 나누어 주고 싶어 한다. 그녀는 포장을 뜯고 싶지 않고, 어떤 아이만 다른 아이와 다른 개수의 사탕을 받는 것도 원하지 않는다. 다만 한 아이가 서로 다른 포장을 여러 개 받는 것은 괜찮다.

도와줄 수 있는가? 모든 포장을 나누었을 때 각 아이가 같은 개수의 사탕을 받게 되는 아이 수의 최댓값을 구하는 프로그램을 작성하라.

입력

첫 번째이자 유일한 줄에 자연수 $N$ ( $1 \le N \le 200000$ )이 주어진다. 이는 Bajtek이 준비한 포장의 개수이다.

출력

출력의 첫 번째 줄에는 선물을 받을 수 있는 아이의 최대 인원 수 $R$ 을 쓴다. 다음 $R$ 개의 줄에는 아이마다 한 줄씩 선물을 적는다. $i$ 번째 아이에 대한 설명은 그 아이가 받는 포장의 개수 $R_i$ 로 시작하고, 한 칸의 빈칸 뒤에 그 아이에게 준 포장들에 든 사탕 개수를 나타내는 자연수 $R_i$ 개가 이어진다.

해가 여러 개라면 그중 어떤 것을 출력해도 된다.

예제2

예제 1
입력
```
3
```
예상 출력
```
2
2 1 2
1 3
```
예제 2
입력
```
4
```
예상 출력
```
2
2 1 4
2 2 3
```