Problem C: P8148 声海 | Sea of Voices
Memory Limit：128 MB
Time Limit：2.000 S
Judge Style：Text Compare
Creator：
Submit：32
Solved：5
Description
## 题目背景
「真是，如梦似幻呢。」
“怎么？”
「我看见你从开始到现在的一切记忆；看见你，从一次次或欢喜或失落中走来。那些场景在我眼前浮现，像梦，却又那么模糊——我只听见那些声音，只感到那片声音的海洋将我环围… 你听得见吗？」
“当然。毕竟，它们是我的记忆啊。”
「或许，一次生命，便是一场发声的历程吧。我们诞生时的啼哭，便在向世界发出宣告降临的声音；在一次次挑战的过程中，我们向一切阻碍我们的事物唱出不屈的战歌；在日常的点滴中，我们向所珍视之人倾诉内心深处的话语… 这样的声音，这样的感情，是不是就是我们所生存世界的本质呢？」
“或许就是这样吧。纵使一路走来，我们看见了无尽的景色，但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。”
「是啊… 但愿，在这片声音的海洋里，你不会迷失你的方向。我期许着听见更多，关于你的声音。怀揣着这种信念，向前走下去吧。」
“你也一样。”
> 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
>
> 然后成为掠影，散失在虚无之中
## 题目描述
“但是… 曾有一些人，在我的生命里留下了重要的声音，我却无法回忆起了…”
「为什么呢？」
“不妨让我们把问题变得形式化一点。我想回忆起的声音有 $n$ 个，它们的共鸣度——非负整数 $a_i$，是单调不降的。最初它们互不干涉，但随着时间的推移，多个相邻的声音会交织在一起形成新的声音——也就是说，对于任意的 $1\le l\le r\le n$，第 $l$ 一直到第 $r$ 个声音会交织在一起形成新的声音，而这个声音的共鸣度便是这些声音共鸣度的总和。”
「也就是说，例如 $n=3$，$a=[124]$，那么最终 $\dfrac{3\times(3+1)}2=6$ 个声音的共鸣度分别是 $124367$？」
“没错。现在我把最终所有声音的共鸣度无序地告诉你，你能帮我还原最开始 $n$ 个声音的共鸣度吗？”
「乐意之至。」
### 简要题意
$a$ 为长度为 $n$ 的非负整数序列，满足 $\forall 1<i\le na_{i-1}\le a_i$。现 **无序** 地给出 **可重集** $S=\left\{\sum_{k=l}^r a_k|1\le l\le r\le n\right\}$，试还原 $a$。
## 输入格式
第一行一个正整数 $n$，代表最初声音的个数。
接下来一行 $\dfrac{n\times(n+1)}2$ 个非负整数，表示现在所有声音的共鸣度（输入无序）。
## 输出格式
一行 $n$ 个非负整数，表示最初 $n$ 个声音共鸣度 $a_i$。
## 输入输出样例 #1
### 输入 #1
```
3
1 2 3 4 6 7
```
### 输出 #1
```
1 2 4
```
## 输入输出样例 #2
### 输入 #2
```
5
1 3 4 7 8 9 10 11 15 17 18 19 24 27 28
```
### 输出 #2
```
1 3 7 8 9
```
## 说明/提示
对于全部数据，有 $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）：无特殊限制。
「真是，如梦似幻呢。」
“怎么？”
「我看见你从开始到现在的一切记忆；看见你，从一次次或欢喜或失落中走来。那些场景在我眼前浮现，像梦，却又那么模糊——我只听见那些声音，只感到那片声音的海洋将我环围… 你听得见吗？」
“当然。毕竟，它们是我的记忆啊。”
「或许，一次生命，便是一场发声的历程吧。我们诞生时的啼哭，便在向世界发出宣告降临的声音；在一次次挑战的过程中，我们向一切阻碍我们的事物唱出不屈的战歌；在日常的点滴中，我们向所珍视之人倾诉内心深处的话语… 这样的声音，这样的感情，是不是就是我们所生存世界的本质呢？」
“或许就是这样吧。纵使一路走来，我们看见了无尽的景色，但只有那些与我们内心共鸣的声音——或来自于自然、或来自于他人的灵魂——才会真正地改变我们自己。”
「是啊… 但愿，在这片声音的海洋里，你不会迷失你的方向。我期许着听见更多，关于你的声音。怀揣着这种信念，向前走下去吧。」
“你也一样。”
> 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
>
> 然后成为掠影，散失在虚无之中
## 题目描述
“但是… 曾有一些人，在我的生命里留下了重要的声音，我却无法回忆起了…”
「为什么呢？」
“不妨让我们把问题变得形式化一点。我想回忆起的声音有 $n$ 个，它们的共鸣度——非负整数 $a_i$，是单调不降的。最初它们互不干涉，但随着时间的推移，多个相邻的声音会交织在一起形成新的声音——也就是说，对于任意的 $1\le l\le r\le n$，第 $l$ 一直到第 $r$ 个声音会交织在一起形成新的声音，而这个声音的共鸣度便是这些声音共鸣度的总和。”
「也就是说，例如 $n=3$，$a=[124]$，那么最终 $\dfrac{3\times(3+1)}2=6$ 个声音的共鸣度分别是 $124367$？」
“没错。现在我把最终所有声音的共鸣度无序地告诉你，你能帮我还原最开始 $n$ 个声音的共鸣度吗？”
「乐意之至。」
### 简要题意
$a$ 为长度为 $n$ 的非负整数序列，满足 $\forall 1<i\le na_{i-1}\le a_i$。现 **无序** 地给出 **可重集** $S=\left\{\sum_{k=l}^r a_k|1\le l\le r\le n\right\}$，试还原 $a$。
## 输入格式
第一行一个正整数 $n$，代表最初声音的个数。
接下来一行 $\dfrac{n\times(n+1)}2$ 个非负整数，表示现在所有声音的共鸣度（输入无序）。
## 输出格式
一行 $n$ 个非负整数，表示最初 $n$ 个声音共鸣度 $a_i$。
## 输入输出样例 #1
### 输入 #1
```
3
1 2 3 4 6 7
```
### 输出 #1
```
1 2 4
```
## 输入输出样例 #2
### 输入 #2
```
5
1 3 4 7 8 9 10 11 15 17 18 19 24 27 28
```
### 输出 #2
```
1 3 7 8 9
```
## 说明/提示
对于全部数据，有 $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）：无特殊限制。
Sample Input Copy
Sample Output Copy