English · Original
Chinese · Translation
Formal · Original
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.
## Input
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).
## Output
Print _n_ integers: for each astronomer print the number of time segments describer earlier.
[samples]
## 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.
在研究了信标之后，Mister B 决定访问外星人的星球，因为他了解到他们生活在一个闪烁的恒星月亮系统中。此外，Mister B 学到，这颗恒星恰好每 #cf_span[T] 秒闪烁一次。问题是，这颗恒星尚未被科学家们发现。
有 #cf_span[n] 位天文学家，编号从 #cf_span[1] 到 #cf_span[n]，试图探测这颗恒星。他们通过发送请求来记录天空持续 #cf_span[1] 秒来尝试探测。
天文学家们按循环方式发送请求：第 #cf_span[i] 位天文学家在第 #cf_span[(i - 1)] 位之后恰好 #cf_span[ai] 秒发送请求（即，如果前一个请求在时刻 #cf_span[t] 发送，则下一个请求在时刻 #cf_span[t + ai] 发送）；第 #cf_span[1] 位天文学家比第 #cf_span[n] 位晚 #cf_span[a1] 秒发送请求。第一位天文学家在时刻 #cf_span[0] 发送他的第一个请求。
Mister B 不知道恒星首次闪烁的确切时刻，但显然，恒星所有将要闪烁的时刻都由其在区间 #cf_span[[0, T)] 内的闪烁时刻决定。此外，该区间可以划分为 #cf_span[T] 个长度为 #cf_span[1] 秒的片段，每个片段形式为 #cf_span[[t, t + 1))，其中 #cf_span[t = 0, 1, 2, ..., (T - 1)]。
Mister B 想知道每位天文学家首次发现恒星的可能性有多大。
对于每位天文学家，计算在区间 #cf_span[[0, T)] 中有多少个形式为 #cf_span[[t, t + 1))（#cf_span[t = 0, 1, 2, ..., (T - 1)]）的片段，使得如果恒星首次闪烁发生在该时间段内，则该天文学家将是第一个发现恒星的人。
第一行包含两个整数 #cf_span[T] 和 #cf_span[n]（#cf_span[1 ≤ T ≤ 109]，#cf_span[2 ≤ n ≤ 2·105]）。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。
请输出 #cf_span[n] 个整数：对每位天文学家，输出前述描述的时间片段数量。
在第一个样例中，第一位天文学家在时刻 #cf_span[t1 = 0, 5, 10, ...] 发送请求，第二位在时刻 #cf_span[t2 = 3, 8, 13, ...] 发送请求。因此，在区间 #cf_span[[0, 1)) 中，第一位天文学家在时刻 #cf_span[t1 = 0] 首先发现；在 #cf_span[[1, 2)) 中，第一位天文学家在时刻 #cf_span[t1 = 5] 首先发现；在 #cf_span[[2, 3)) 中，第一位天文学家在时刻 #cf_span[t1 = 10] 首先发现；而在 #cf_span[[3, 4)) 中，第二位天文学家在时刻 #cf_span[t2 = 3] 首先发现。
在第二个样例中，区间 #cf_span[[0, 1)) — 第一位天文学家首先发现，#cf_span[[1, 2)) — 第二位天文学家，#cf_span[[2, 3)) — 第三位天文学家，#cf_span[[3, 4)) — 第四位天文学家，#cf_span[[4, 5)) — 第一位天文学家。
## Input
第一行包含两个整数 #cf_span[T] 和 #cf_span[n]（#cf_span[1 ≤ T ≤ 109]，#cf_span[2 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。
## Output
请输出 #cf_span[n] 个整数：对每位天文学家，输出前述描述的时间片段数量。
[samples]
## Note
在第一个样例中，第一位天文学家在时刻 #cf_span[t1 = 0, 5, 10, ...] 发送请求，第二位在时刻 #cf_span[t2 = 3, 8, 13, ...] 发送请求。因此，在区间 #cf_span[[0, 1)) 中，第一位天文学家在时刻 #cf_span[t1 = 0] 首先发现；在 #cf_span[[1, 2)) 中，第一位天文学家在时刻 #cf_span[t1 = 5] 首先发现；在 #cf_span[[2, 3)) 中，第一位天文学家在时刻 #cf_span[t1 = 10] 首先发现；而在 #cf_span[[3, 4)) 中，第二位天文学家在时刻 #cf_span[t2 = 3] 首先发现。
在第二个样例中，区间 #cf_span[[0, 1)) — 第一位天文学家首先发现，#cf_span[[1, 2)) — 第二位天文学家，#cf_span[[2, 3)) — 第三位天文学家，#cf_span[[3, 4)) — 第四位天文学家，#cf_span[[4, 5)) — 第一位天文学家。
**Definitions**
Let $ T \in \mathbb{Z}^+ $ be the period of the star’s flickering.
Let $ n \in \mathbb{Z}^+ $ be the number of astronomers.
Let $ \mathbf{a} = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the cycle of intervals between consecutive requests, where astronomer $ i $ sends a request every $ a_i $ seconds.
The request times of astronomer $ i $ are:
$$
R_i = \left\{ t \in \mathbb{R}_{\ge 0} \mid t \equiv \sum_{j=1}^{i-1} a_j \pmod{T} \right\}
$$
with the convention that $ \sum_{j=1}^{0} a_j = 0 $.
Let $ S_t = [t, t+1) $ for $ t \in \{0, 1, \dots, T-1\} $ be the time segments of interest.
**Constraints**
1. $ 1 \le T \le 10^9 $
2. $ 2 \le n \le 2 \cdot 10^5 $
3. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each astronomer $ i \in \{1, \dots, n\} $, compute:
$$
c_i = \left| \left\{ t \in \{0, 1, \dots, T-1\} \ \middle| \ \min_{j \in \{1,\dots,n\}} \left( \left( \sum_{k=1}^{j} a_k \mod T \right) - t \right) \mod T = \sum_{k=1}^{i} a_k \mod T \right\} \right|
$$
where the minimum is taken over the smallest non-negative residue of $ (r_j - t) \mod T $, and $ r_j = \sum_{k=1}^{j} a_k \mod T $ is the offset of astronomer $ j $'s first request within $[0, T)$.
Equivalently, define $ r_0 = 0 $, and for $ i \in \{1, \dots, n\} $, let $ r_i = \left( \sum_{k=1}^{i} a_k \right) \mod T $.
Then for each $ t \in \{0, 1, \dots, T-1\} $, assign $ t $ to the astronomer $ i $ such that $ r_i $ is the smallest value $ \ge t $ (cyclically), i.e., the first request time $ \ge t $ in the circular timeline $ \mathbb{Z}_T $.
Then $ c_i $ is the number of $ t \in \{0, 1, \dots, T-1\} $ for which astronomer $ i $ is the first to observe the star.
API Response (JSON)
{
"problem": {
"name": "D. Mister B and Astronomers",
"description": {
"content": "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 exac",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF819D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 exac...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在研究了信标之后，Mister B 决定访问外星人的星球，因为他了解到他们生活在一个闪烁的恒星月亮系统中。此外，Mister B 学到，这颗恒星恰好每 #cf_span[T] 秒闪烁一次。问题是，这颗恒星尚未被科学家们发现。\n\n有 #cf_span[n] 位天文学家，编号从 #cf_span[1] 到 #cf_span[n]，试图探测这颗恒星。他们通过发送请求来记录天空持续 #cf_span[1]...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T \\in \\mathbb{Z}^+ $ be the period of the star’s flickering. \nLet $ n \\in \\mathbb{Z}^+ $ be the number of astronomers. \nLet $ \\mathbf{a} = (a_1, a_2, \\dots, a_n) \\in \\mathbb{...",
"is_translate": false,
"language": "Formal"
}
]
}