声海 | Sea of Voices

“但是… 曾有一些人，在我的生命里留下了重要的声音，我却无法回忆起了…” 「为什么呢？」 “不妨让我们把问题变得形式化一点。我想回忆起的声音有 $n$ 个，它们的共鸣度——非负整数 $a_i$，是单调不降的。最初它们互不干涉，但随着时间的推移，多个相邻的声音会交织在一起形成新的声音——也就是说，对于任意的 $1\le l\le r\le n$，第 $l$ 一直到第 $r$ 个声音会交织在一起形成新的声音，而这个声音的共鸣度便是这些声音共鸣度的总和。” 「也就是说，例如 $n=3$，$a=[1,2,4]$，那么最终 $\dfrac{3\times(3+1)}2=6$ 个声音的共鸣度分别是 $1,2,4,3,6,7$？」 “没错。现在我把最终所有声音的共鸣度无序地告诉你，你能帮我还原最开始 $n$ 个声音的共鸣度吗？” 「乐意之至。」 ### 简要题意 $a$ 为长度为 $n$ 的非负整数序列，满足 $\forall 1<i\le n,a_{i-1}\le a_i$。现 **无序** 地给出 **可重集** $S=\left\{\sum_{k=l}^r a_k|1\le l\le r\le n\right\}$，试还原 $a$。 ## Input 第一行一个正整数 $n$，代表最初声音的个数。 接下来一行 $\dfrac{n\times(n+1)}2$ 个非负整数，表示现在所有声音的共鸣度（输入无序）。 ## Output 一行 $n$ 个非负整数，表示最初 $n$ 个声音共鸣度 $a_i$。 [samples] ## Background 「真是，如梦似幻呢。」 “怎么？” 「我看见你从开始到现在的一切记忆；看见你，从一次次或欢喜或失落中走来。那些场景在我眼前浮现，像梦，却又那么模糊——我只听见那些声音，只感到那片声音的海洋将我环围… 你听得见吗？」 “当然。毕竟，它们是我的记忆啊。” 「或许，一次生命，便是一场发声的历程吧。我们诞生时的啼哭，便在向世界发出宣告降临的声音；在一次次挑战的过程中，我们向一切阻碍我们的事物唱出不屈的战歌；在日常的点滴中，我们向所珍视之人倾诉内心深处的话语… 这样的声音，这样的感情，是不是就是我们所生存世界的本质呢？」 “或许就是这样吧。纵使一路走来，我们看见了无尽的景色，但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。” 「是啊… 但愿，在这片声音的海洋里，你不会迷失你的方向。我期许着听见更多，关于你的声音。怀揣着这种信念，向前走下去吧。」 “你也一样。” > We'll see creation come undone > > 我们会见证自己存在的印记被世界拂去 > > These bones that bound us will be gone > > 而那些既有的束缚将不再留存 > > We'll stir our spirits till we're one > > 我们会洗涤自己的灵魂直至合为一体 > > Then soft as shadows we'll become > > 然后成为掠影，散失在虚无之中 ## Note 对于全部数据，有 $1\le n\le 2000$，$0\le a_i\le 10^5$。 Subtask 1（5 pts）：保证 $n=2$。 Subtask 2（15 pts）：保证 $n=3$。 Subtask 3（30 pts）：保证 $n\le 100$。 Subtask 4（50 pts）：无特殊限制。