Number tag exchange

Interview

Time limit2sMemory limit512 MB

Summary

Simulate M bubble passes over the line, swapping neighbors when the front tag has the larger remainder modulo the pass number.

Level: Easy2 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

$N$ students stand in one line in a classroom. The $i$ -th student from the front holds one number tag, and the number written on it is $A_i$ .

There are $M$ cards, numbered 1 to $M$ . The cards are used in order starting from card 1, and card $k$ ( $2 \le k \le M$ ) is used after card $k-1$ has been used.

Card $i$ is used like this.

The teacher gives card $i$ to student 1.
Student $j$ , who holds the card, passes it to student $j+1$ . If $A_j \bmod i$ is greater than $A_{j+1} \bmod i$ , the two students exchange their number tags. Here $A_j$ is the number on the tag student $j$ holds at that moment.
Once the last student receives the card, that card is thrown away.

The game ends when card $M$ has been thrown away. Write a program that prints the number tags the students hold after the game ends, in order from the front of the line.

Input

The first line has the number of students $N$ and the number of cards $M$ , separated by a space. ( $1 \le N \le 100$ , $1 \le M \le 100$ )

Each of the next $N$ lines has the number $A_i$ on the tag that student $i$ starts with. ( $1 \le A_i \le 1000$ )

Output

Print the number on the tag each student holds after the game ends, one per line, in order from the front of the line.

Hint

Suppose six students hold the tags 3, 2, 8, 3, 1, 5 in that order and there are four cards. The line changes as each card is used.

after card 1: 3 2 8 3 1 5
after card 2: 2 8 3 3 1 5
after card 3: 2 3 3 1 8 5
after card 4: 2 3 1 8 5 3

Examples2

Example 1
Input
```
6 4
3
2
8
3
1
5
```
Expected output
```
2
3
1
8
5
3
```

Example 2

Input

Expected output