← 返回题目列表

Codeforces · 819/D

D. B先生和天文学家

中文机器翻译题面 查看原题

在研究了信标之后,B 先生决定访问外星人的星球,因为他了解到他们生活在一个闪烁的恒星月亮系统中。而且,B 先生了解到,星星恰好在 T 秒内发光一次。问题是这颗恒星尚未被科学家发现。

有 n 位天文学家(从 1 到 n)试图探测这颗恒星。他们尝试通过发送记录天空 1 秒的请求来检测恒星。

天文学家循环发送请求:第 i 个天文学家在第 (i - 1) 个天文学家之后的 ai 秒处发送请求(即,如果上一个请求是在时刻 t 发送的,那么下一个请求将在时刻 t + ai 发送);第一个天文学家比第 n 个天文学家晚 1 秒发送请求。第一个天文学家在时刻 0 发送他的第一个请求。

B先生不知道星星会在什么时刻发光,但很明显,星星发光的所有时刻都是由区间[0, T)中其发光时刻的时间决定的。此外,该间隔可以分为 T 个长度为 1 秒的部分,每个部分的形式为 [t, t + 1),其中 t = 0, 1, 2, ..., (T - 1)。

B 先生想知道每位天文学家能够多么幸运地首先发现了这颗恒星。

对于每个天文学家,计算在区间 [0, T) 中有多少个 [t, t + 1) (t = 0, 1, 2, ..., (T - 1)) 形式的片段,以便如果恒星的第一次发光发生在这个时间区间内,则该天文学家是第一个发现恒星的人。

输入

第一行包含两个整数 T 和 n (1 ≤ T ≤ 109, 2 ≤ n ≤ 2·105)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。

输出

打印 n 个整数:为每个天文学家打印前面描述的时间段的数量。

示例

输入 #1

4 2
2 3

输出 #1

3 1

输入 #2

5 4
1 1 1 1

输出 #2

2 1 1 1

注意

在第一个样本测试中,第一个天文学家将在时刻 t1 = 0, 5, 10, ... 发送请求,第二个 — 在时刻 t2 = 3, 8, 13, .... 这就是为什么间隔 [0, 1) 第一个天文学家将在时刻 t1 = 0, [1, 2) 首先发现 — 第一个天文学家在时刻 t1 = 5, [2, 3) — t1 = 10 时刻的第一个天文学家,[3, 4) — t2 = 3 时刻的第二个天文学家。

在第二个样本测试间隔中 [0, 1) — 第一个天文学家将首先发现,[1, 2) — 第二个天文学家,[2, 3) — 第三个天文学家,[3, 4) — 第四个天文学家,[4, 5) — 第一个天文学家。