Mister B and Astronomers
Contest: Codeforces Round 421 (Div. 1)
Difficulty rating: 2900
Tags: number theory

After 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 ai 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 + ai); the 1-st astronomer sends requests a1 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 format:
The first line contains two integers T and n (1 ≤ T ≤ 109, 2 ≤ n ≤ 2·105).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample test the first astronomer will send requests at moments t1 = 0, 5, 10, ..., the second — at moments t2 = 3, 8, 13, .... That's why interval [0, 1) the first astronomer will discover first at moment t1 = 0, [1, 2) — the first astronomer at moment t1 = 5, [2, 3) — the first astronomer at moment t1 = 10, and [3, 4) — the second astronomer at moment t2 = 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.

Example input:
4 2
2 3

Example output:
3 1

Example input:
5 4
1 1 1 1

Example output:
2 1 1 1

Editorial:
Let's construct slow but clear solution and then, speed it up.
Let's denote $$s = \sum_{i=1}^{n} a_i$$. We can see, that, at first, all operation with time are modulo T and the i - th astronomer checks moments sti, (sti + s)%T, (sti + 2s)%T ..., where $$st_i = \sum_{j=2}^{i} a_j$$. More over, every astronomer, who checks moment t will check moment (t + S)%T by next time.
So we now constructed functional graph with T vertices. But this graph has very special type, since it can be divided on some cycles. More specifically, This graph consists of gcd(T, s) oriented cycles and each cycle has length exactly $$\frac{T}{gcd(T,s)}$$. Even more, vertices u and v belong to same cycle iff u ≡ v (mod gcd(T, s)).
So we can work with cycles independently.
Let's look closely on one cycle. It's obviously, that all astronomers will walk on their cycles from their starting positions sti % T. But what the answer for them.
Answer for the i - th astronomer is number of vertices, including starting vertex, to the nearest starting vertex of any other astronomer if count along the orientation of cycle, because if two astronomers came to same vertex, lucky is one, who came first. Other astronomer has this vertex as start, his time is stj, i - th time is sti + k·s, k ≥ 1 and sti + k·s > stj. If sti ≡  stj (mod T) and sti < stj then answer for the j - th astronomer is always 0.
So we must effectively calculate distance between two positions on cycle.
For that, let's numerate vertices along the orientation of cycle using vertex with minimal label as 0. If we will know position of sti% T for every astronomer calculation of distance between consecutive is trivial (sort, or set or other).
For the i - th astronomer let's denote vertex with label 0 in his cycle as zi. zi = sti % gcd(T, s). But cycles very specific, because vertex with label 0 is zi, vertex with label 1 is (zi + s) % T, vertex with label 2 is (zi + 2s) % T. In other words, vertex with label k is (zi + k·s) % T.
If we want to know position k of sti, we need to find v such, that v ≡  (v% gcd(T, s)) + k·s(mod T) which is diofant equation and can be calculated in O(log(T)) time.
Result complexity is O(n·log(T)).