CF819D.Mister B and Astronomers

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 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.

在研究了信标之后，B先生决定拜访外星人的星球，因为他得知他们生活在一颗名为“月星”的闪烁恒星系统中。此外，B先生还了解到，这颗恒星恰好每 $T$ 秒闪耀一次。问题是，这颗恒星尚未被科学家发现。

共有 $n$ 名天文学家，编号从 $1$ 到 $n$，他们正试图探测这颗恒星。他们通过发送请求来记录天空 1 秒钟，以此尝试探测恒星。

天文学家们按循环方式发送请求：第 $i$ 位天文学家在第 $(i-1)$ 位之后恰好 $a_i$ 秒发送请求（即若上一次请求在时刻 $t$ 发出，则下一次请求在时刻 $t + a_i$ 发出）；第 $1$ 位天文学家则在第 $n$ 位之后 $a_1$ 秒发送请求。第 $1$ 位天文学家的首次请求在时刻 $0$ 发出。

B先生并不知道恒星首次闪耀的时刻，但显然，所有恒星将要闪耀的时刻均由其在区间 $[0,\,T)$ 内的首次闪耀时刻完全确定。此外，该区间可划分为 $T$ 个长度为 1 秒的子区间，形式为 $[t,\,t+1)$，其中 $t = 0,\,1,\,2,\,\dots,\,(T-1)$。

B先生希望了解：每位天文学家率先发现恒星的“幸运程度”如何。

对每位天文学家，请计算：在区间 $[0,\,T)$ 中，有多少个形如 $[t,\,t+1)$（其中 $t = 0,\,1,\,2,\,\dots,\,(T-1)$）的子区间，使得若恒星首次闪耀发生在该子区间内，则该天文学家是首位探测到恒星的人。

The first line contains two integers T and n (1 ≤ T ≤ 109, 2 ≤ n ≤ 2·105).

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含两个整数 $T$ 和 $n$（$1 \leq T \leq 10^9$，$2 \leq n \leq 2\cdot10^5$）。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^9$）。

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

输出 n 个整数：对每位天文学家，输出前述的时间段数量。

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.

在第一个样例测试中，第一位天文学家将在时刻 $t_1 = 0, 5, 10, \dots$ 发送请求，第二位天文学家将在时刻 $t_2 = 3, 8, 13, \dots$ 发送请求。因此，在区间 $[0, 1)$ 内，第一位天文学家将在时刻 $t_1 = 0$ 首次发现；在区间 $[1, 2)$ 内，第一位天文学家将在时刻 $t_1 = 5$ 首次发现；在区间 $[2, 3)$ 内，第一位天文学家将在时刻 $t_1 = 10$ 首次发现；而在区间 $[3, 4)$ 内，第二位天文学家将在时刻 $t_2 = 3$ 首次发现。

在第二个样例测试中，区间 $[0, 1)$ — 第一位天文学家首次发现；区间 $[1, 2)$ — 第二位天文学家首次发现；区间 $[2, 3)$ — 第三位天文学家首次发现；区间 $[3, 4)$ — 第四位天文学家首次发现；区间 $[4, 5)$ — 第一位天文学家首次发现。