In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 23rd
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]


[AED031] Golden Permits

(this problem is an adaptation from a MIUP'2015 problem)

The Interior Ministry has decided to develop a new more exciting and fairer system for awarding the fabled Golden Resident Permits, whilst also giving less wealthy candidates a possibility of winning. The idea is that candidates for a permit buy lottery tickets which are numbered 1 up to some maximum number N. The lottery system then consists of a series of rounds where certain numbers are eliminated or knocked out until only some remain.

The basic idea of the elimination system in the lottery is similar to the old Roman imperial legion system of decimating. Here the system is not quite so brutal. The lottery system consists of simply eliminating every K’th ticket and then repeating the process until there are only W tickets remaining. These are the winning tickets.

On a live TV show the elimination factor is announced and then candidates can watch the process evolve over time and see if they win the desired golden resident permit. Of course any system is open to abuse and this is no exception. Your job is, given the right insider information, to advise certain clients what number they should buy.

The Problem

You will be given the number N of the tickets which are initially ordered 1...N. In fact they are arranged logically in a circle so that counting continues in a circular fashion. You are also given the value K, the elimination factor, and W, the number of winning tickets. Your job is to find the winning tickets.

Input

The input consists of three integer values, on separate lines, namely the number of tickets N, the elimination factor K, and and the number of winning tickets W.

Output

The output consists of W lines, each containing one of the winning tickets. Thee tickets should come in increasing order.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

5 ≤ N ≤ 108       Number of initial lottery tickets
1 ≤ K ≤ 108       Elimination factor
1 ≤ W ≤ 5       Number of winning tickets

Example Input 1 Example Output 1
10
3
2
4
10

Explanation of Example Input 1

We have N=10 and K=3.
In the first round the tickets 3,6,9 are eliminated leaving 1 2 4 5 7 8 10
The next round eliminates 2 and 7 leaving 1 4 5 8 10
The next round eliminates 1 and 8 leaving 4 5 10
The next round eliminates 5 leaving 4 and 10, which are the winning tickets.


Example Input 2 Example Output 2
98
11
5
19
27
72
89
90

Example Input 3 Example Output 3
987654
1234
4
116753
624596
692337
750742


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto