AIOC Banner

Problem: IOI Team Selection

Want to try solving this problem? You can submit your code online if you log in or register.


IOI Team Selection

Input File: teamin.txt
Output File: teamout.txt
Time Limit: 1 second
Memory Limit: 32 MB

It is the night before the IOI team selection is to be announced. All the students are awake and confident, eagerly anticipating the results. Looking through the exam scores, however, Bernard begins to worry. Every student has achieved a perfect score on the exam, making it impossible to determine who should be on the team.

Shutting the lid of his laptop, Bernard announces that team selection this year will take place a little differently. The process will start by Bernard announcing a number, k, and then have all the students stand in a circle. Bernard will then, starting with the first student in the circle, move around the circle removing every kth student until the circle is empty. The last four students removed from the circle will form the team.

You decide that if you want to make the team, you will have to act fast and ensure you stand in one of the four selected positions in the circle. Your task is to write a program that, given the number of students in the circle and the number k, will determine the last four positions to be selected by Bernard.

Input

The input will be a single line consisting of two integers, n k, separated by a single space (4 <= n <= 10,000,000, 1 <= k <= 10,000,000). n represents the number of students in the circle, while k represents how often Bernard removes a student.

Output

The output should consist of a single line with four integers, each separated by a single space. These integers are the last four positions in the circle to be removed by Bernard. These positions should be listed in the order in which Bernard removes them.

Sample Input 1

9 3

Sample Output 1

5 2 7 1

Sample Input 2

11 7

Sample Output 2

6 1 4 5

Explanation

In the first sample input, there are n=9 students in the circle and k=3. The students are removed from the circle in the order 3, 6, 9, 4, 8, 5, 2, 7, 1. The last four students to be removed are 5, 2, 7 and 1. These students form the team.

Diagram of students in a circle being chosen

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 25 February 2021,  5:06am AEDT