Caki

Interview

Time limit1sMemory limit512 MB

Summary

Given a list of overtake events, track car positions on a loop to find the final top six finishers.

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

Problem

Little Caki loves Formula 1 races, and the new season has just started. Last Sunday Caki sat in front of the barn, pulled out the antenna of his radio, pointed it at a nearby relay tower, and listened closely to the race broadcast. Everything would have been fine if the commentator had not decided to play a joke on his listeners. At the start of the broadcast he announced that the only information he would put on the air was the number of a car that overtakes the car in front of it, given at the exact moment of the overtake. The race track is a loop, and we assume that every car reached the finish after driving the required number of laps.

From this information, determine which cars took the first six places at the end of the race. Note that a car may overtake other cars while being a full lap or more ahead of them.

"The car in front of it" means the car driving directly ahead of it on the track. If, just before the overtake, the overtaken car was ahead of the overtaking car in the race by less than one lap, the two cars swap places in the standings. Otherwise the standings do not change: either the overtaking car was already ahead and is lapping a car that is a lap behind, or the overtaken car was ahead by a lap or more.

Input

The first line contains two positive integers $n$ and $k$ ( $2 \le n \le 1\,000$ , $1 \le k \le 10\,000$ ): the number of cars on the track and the number of overtakes during the race. The cars are numbered from 1 to $n$ , and each car's number is its starting position (car 1 starts at the front).

Each of the next $k$ lines contains one positive integer $x$ ( $1 \le x \le n$ ), the number of a car that overtook the car in front of it. These $k$ numbers are given in the order in which the overtakes happened.

Output

On the first line, print the numbers of the cars that took the first six places at the end of the race. The first number is the car in first place, and the sixth number is the car in sixth place. Separate the numbers with single spaces. If there are fewer than six cars, print exactly as many numbers as there were cars in the race.

Examples3

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