在研究了信标之后,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) — 第一个天文学家。