Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Mister B and Astronomers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter studying the beacons Mister B decided to visit alien's planet, because he learned that they live in a system of flickering star Moon. Moreover, Mister B learned that the star shines once in exactly *T* seconds. The problem is that the star is yet to be discovered by scientists.

There are *n* astronomers numerated from 1 to *n* trying to detect the star. They try to detect the star by sending requests to record the sky for 1 second.

The astronomers send requests in cycle: the *i*-th astronomer sends a request exactly *a*_{i} second after the (*i* - 1)-th (i.e. if the previous request was sent at moment *t*, then the next request is sent at moment *t* + *a*_{i}); the 1-st astronomer sends requests *a*_{1} seconds later than the *n*-th. The first astronomer sends his first request at moment 0.

Mister B doesn't know the first moment the star is going to shine, but it's obvious that all moments at which the star will shine are determined by the time of its shine moment in the interval [0, *T*). Moreover, this interval can be split into *T* parts of 1 second length each of form [*t*, *t* + 1), where *t* = 0, 1, 2, ..., (*T* - 1).

Mister B wants to know how lucky each astronomer can be in discovering the star first.

For each astronomer compute how many segments of form [*t*, *t* + 1) (*t* = 0, 1, 2, ..., (*T* - 1)) there are in the interval [0, *T*) so that this astronomer is the first to discover the star if the first shine of the star happens in this time interval.

Input

The first line contains two integers *T* and *n* (1 ≤ *T* ≤ 10^{9}, 2 ≤ *n* ≤ 2·10^{5}).

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}).

Output

Print *n* integers: for each astronomer print the number of time segments describer earlier.

Examples

Input

4 2

2 3

Output

3 1

Input

5 4

1 1 1 1

Output

2 1 1 1

Note

In the first sample test the first astronomer will send requests at moments *t*_{1} = 0, 5, 10, ..., the second — at moments *t*_{2} = 3, 8, 13, .... That's why interval [0, 1) the first astronomer will discover first at moment *t*_{1} = 0, [1, 2) — the first astronomer at moment *t*_{1} = 5, [2, 3) — the first astronomer at moment *t*_{1} = 10, and [3, 4) — the second astronomer at moment *t*_{2} = 3.

In the second sample test interval [0, 1) — the first astronomer will discover first, [1, 2) — the second astronomer, [2, 3) — the third astronomer, [3, 4) — the fourth astronomer, [4, 5) — the first astronomer.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2018 02:42:09 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|