题目描述

有 $n$ 块木板，长度依次为 $a_1,a_2,\dots,a_n$。给定一个高度 $b$ 时，每块木板会被从左到右切成若干段：尽量切出长度为 $b$ 的段，最后剩下一段长度 $c$，其中 $1\le c\le b$，也会被加入篱笆。

所有木板按原顺序切开并拼接成一长串篱笆。主人从最左边开始，将第 1、3、5、... 段涂成白色。对所有可能的 $b=1,2,\dots,M$，其中 $M=\max a_i$，求需要涂白的总长度。

输入格式

第一行整数 $z$。每组数据第一行整数 $n$，接下来给出 $n$ 个整数 $a_i$。

输出格式

每组数据输出 $M$ 行，第 $i$ 行表示 $b=i$ 时的答案。

Samples

1
4
10 7 2 8

14
13
15
13
15
16
21
23
24
12

数据范围

$1\le z\le5$，$1\le n\le10^6$，$1\le a_i\le10^6$，且每组数据 $\sum a_i\le10^6$。