Description

“但是… 曾有一些人，在我的生命里留下了重要的声音，我却无法回忆起了…”

「为什么呢？」

“不妨让我们把问题变得形式化一点。我想回忆起的声音有 $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 Format

第一行一个正整数 $n$，代表最初声音的个数。

接下来一行 $\dfrac{n\times(n+1)}2$ 个非负整数，表示现在所有声音的共鸣度（输入无序）。

Output Format

一行 $n$ 个非负整数，表示最初 $n$ 个声音共鸣度 $a_i$。

3
1 2 3 4 6 7

1 2 4

5
1 3 4 7 8 9 10 11 15 17 18 19 24 27 28

1 3 7 8 9

Hint

对于全部数据，有 $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）：无特殊限制。