프로그램 명: coci_cokolade
제한시간: 2 초

‘사탕 박람회’에서 가장 흥미로운 부스는 ‘캔디런’이다. ‘캔디런’ 부스에는 총 N개의 바구니가 있어서 각 바구니에 bi 개의 사탕이 있다. 각 날마다 관람객들은 선착순으로 각 바구니에 줄을 선다. 사람이 어느 정도 왔으면 사회자는 각 바구니에 있는 사탕을 꺼내서 앞 사람부터 사탕을 나눠준다. 이때 첫 번째 날에는 1개씩 나눠주고, 두 번째 날에는 2개씩, …, k번째 날에는 k개씩 나눠주게 된다.

‘캔디런’ 부스의 관리자인 DevSweets는 매 날마다 줄어든 사탕의 수가 같은 몇 개의 바구니가 있다는 것을 깨달았다. 이에 더 나아가서 DevSweets는 1 이상 N 이하의 자연수 a에 대해서 줄어든 사탕의 수가 같은 정확히 a개의 바구니가 존재하는 최초의 날을 알아보려고 한다. DevSweets의 궁금증을 해결하는 프로그램을 작성하여라.

입력 형식

출력 형식

a번째 줄에, 줄어든 사탕의 수가 같은 정확히 a개의 바구니가 존재하는 최초의 날의 번호를 출력한다. 만약 그런 날이 없다면 -1을 출력한다. 
출력 예 1
5
11 10 9 6 4

입력 예 1

1
2
3
6
12

입력 예 2

8
12 16 95 96 138 56 205 84

출력 예 2

1
5
14
49
96
97
139
206


입력 예 3

3
5 5 5

출력 예 3

-1
-1
1
입력 예 1 설명 입력 예 3 설명 바구니에 든 사탕의 수가 모두 같기 때문에 세 바구니에서 줄어든 사탕의 수가 항상 같게 된다.
Mirko is a party animal, so he has decided to organise an endless amount of parties for his friends. To satisfy the party's needs, he has decided to set up N tables with candy on them. We know the number of candies bi on each table. On the first day of the rest of eternity, Mirko is going to invite one friend per table, on the second day he will invite two friends per table, on the third day three friends... In general, obviously, on the kth day he is going to invite k friends per each table.

When his friends enter the room, k people will sit down at each table and they will divide the candies on their table in k as large as possible equal pieces, and get rid of the possible remains. After the candy division, because of jealousy and various other reasons, only tables with the same amount of candy per capita will socialise together. Mirko has all eternity to study the social dynamics of his parties. Firstly, he wants to know the answer to the following question: given an s between 1 and N, what is the earliest day when there is a group of exactly s tables socialising together?

As usual, Mirko is incapable of solving his own problems, so every few days he comes to you and asks you what the required number is, given an s. Alas, he has all eternity to ask questions, but you don't. Therefore, you are going to write a programme which outputs Mirko's required answers for each s from 1 to N.

Please note: Before each party, Mirko renews the candy supply on each table, meaning the supplies are equal to those before the first party. Additionally, all people leave from the current party before the next one starts.

INPUT

OUTPUT

Output N lines, each line containing a single integer.

The sth line should contain the required number for a group sized s or -1 if there will never be a group of that size.

SAMPLE TESTS 

input

5
11 10 9 6 4

output

1
2
3
6
12

input

3
5 5 5

output

-1
-1
1

input

8
12 16 95 96 138 56 205 84

output

1
5
14
49
96
97
139
206
Clarification of the first example: On the first day, each table will socialise only with itself so the answer for groups sized 1 is 1. Already on the second day, people sitting at tables 1 and 2 are going to get 5 candies per capita and socialise together, so the answer for a group sized 2 is 2. On the third day, tables 1, 2 and 3 will socialise (because they all have 3 candies per capita). On the sixth day, tables 1, 2, 3 and 4 will socialise (because they now have 1 candy per capita). Finally, on the twelfth day, all tables will socialise together because they will all get zero candy per capita. Clarification of the second example: All tables have the same amount of candy per capita, so a group sized less than 3 will never exist. 
출처:coci/2013-2014/contest4
번역:functionx
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]