Hotel Room Assignment

Interview

Time limit1sMemory limit128 MB

Summary

Simulate assigning arriving groups to hotel rooms with two beds each, filling empty rooms first then pairing singles, and output the final occupancy per room.

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

Problem

A hotel has N rooms, each with two beds, numbered from 1 to N.

When a group of guests arrives, they are accommodated as follows:

While there are empty rooms, each pair of guests is placed in the empty room with the lowest number.
If a group has an odd number of guests, the last remaining guest is placed alone in the empty room with the lowest number.
Once there are no empty rooms left, each remaining guest is placed in the lowest-numbered room currently occupied by exactly one guest, sharing it with a guest from another group.

The hotel is initially empty, and the order in which the groups arrive is known in advance. Write a program that determines how many guests each room holds after the last guest has been accommodated.

Input

The first line contains two integers N and G separated by a space (1 ≤ N ≤ 100). N is the number of rooms in the hotel and G is the number of guest groups.

Each of the next G lines contains the number of guests in one group: the (i+1)-th line gives the number of guests in the i-th group, where groups are numbered by their order of arrival.

The total number of guests (the sum over all groups) is at most the total number of beds in the hotel.

Output

Print N lines. The i-th line contains the number of guests in room i after all guests have been accommodated.

Examples3

Example 1
Input
```
7 3
3
1
4
```
Expected output
```
2
1
1
2
2
0
0
```
Example 2
Input
```
5 4
3
1
1
4
```
Expected output
```
2
2
2
1
2
```
Example 3
Input
```
8 7
3
1
3
2
1
3
1
```
Expected output
```
2
2
2
2
1
2
1
2
```