Bajtur 国王，Bitocja 的统治者，正梦见征服 Bitocja。在他的梦中，就像在现实世界中一样，他距离击败对手还很遥远。因此，他正在思考能做些什么来削弱敌国……

在他的梦中，Bitocja 由 $n$ 个城市（编号为 $1$ 到 $n$）组成，这些城市通过 $n-1$ 条双向道路连接，使得任意两个城市之间都可以通过这些道路到达。换句话说，Bitocja 的地图构成了一棵树。然而，Bajtur 并不完全记得 Bitocja 的道路网络……因此，他的大脑生成了一个随机的道路网络。

国王得出的结论是，强行将 Bitocja 分割成 $k$ 个较小的国家是一个好主意。所谓分割，Bajtur 指的是秘密摧毁恰好 $k-1$ 条道路，这将迫使 Bitocja 分裂成 $k$ 个国家，这些国家是删除所选边后形成的图的连通分量。

然而，对国王来说，仅仅摧毁任意 $k-1$ 条道路是不够的。Bitocja 的每个城市都有一个军事系数 $a_i$——这也是由 Bajtur 的大脑随机生成的。Bajtur 知道，一个国家的军事实力越强，对 Bajtocja 的威胁就越大。具体来说：如果某个国家中各城市军事系数之和为 $S$，则该国家造成的威胁等于 $S^2$。Bajtocja 的总威胁等于所有 $k$ 个国家造成的威胁之和。

现在，Bajtur 向你——他梦中的（字面意义上的！）程序员——求助。请帮他计算，在分割成 $k$ 个国家后，Bitocja 可能产生的最小总威胁是多少。由于 Bajtur 尚未决定参数 $k$ 的值，请计算所有 $k$ 从 $1$ 到 $n$ 的结果。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示 Bajtur 的梦（测试用例）的数量。接下来是各个测试用例的描述；每个测试用例的格式相同。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 300$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)。 接下来的 $n-1$ 行描述了 Bitocja 的道路；第 $i$ 行包含两个整数 $b_i$ 和 $c_i$ ($1 \le b_i, c_i \le n$)，表示连接编号为 $b_i$ 和 $c_i$ 的城市的道路。每个测试用例描述的图都是一棵树。

Bajtur 通过手动选择 $t$ ($1 \le t \le 10$)、整数区间 $[n_{\min}, n_{\max}]$ ($2 \le n_{\min} \le n_{\max} \le 300$) 以及 $a_{\max}$ ($1 \le a_{\max} \le 10^6$) 来生成测试数据。随后，每个测试用例均由他按以下方式独立生成： 城市数量 $n$ 从区间 $[n_{\min}, n_{\max}]$ 中均匀随机选择。 每个数字 $a_1, a_2, \dots, a_n$ 均从区间 $[1, a_{\max}]$ 中独立且均匀随机选择。 * 生成一个自然数序列 $(p_1, p_2, \dots, p_{n-2})$；序列中的每个元素均从区间 $[1, n]$ 中独立且均匀随机选择。Bajtur 将其连接网络视为一棵 Prüfer 编码为 $(p_1, p_2, \dots, p_{n-2})$ 的树。

你可以在 SIO2 系统的“文件”部分找到该任务的示例测试生成器。生成器依次接收以下输入：生成器种子以及数字 $t, n_{\min}, n_{\max}, a_{\max}$。该任务的所有测试都将使用等效代码生成（即使用与编译器实现无关的独立伪随机数库）。

为了确保测试的随机性，每个测试的 $t, n_{\min}, n_{\max}, a_{\max}$ 值均为手动选择，且生成器种子是随机选择的。

输出格式

输出应包含 $t$ 行，描述后续测试用例的答案。每个测试用例的答案应位于单独的一行中，并包含 $n$ 个整数（其中 $n$ 是给定测试用例中的城市数量）；其中第 $k$ 个数字应表示分割成 $k$ 个国家后可能产生的最小威胁。

样例

输入 1

2
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1

输出 1

1089 545 371 287 227 211 203
324 164 114 102 94

说明 1

上述测试是使用 SIO2 系统“文件”部分中提供的代码通过试运行生成的，种子为 $8\,122\,020$，参数为 $t = 2, n_{\min} = 5, n_{\max} = 7, a_{\max} = 10$。

对于第一个测试用例，输出的第一个数字是 $(9+1+4+2+6+4+7)^2 = 1089$，表示未分割的 Bitocja 造成的总威胁。输出的第二个数字对应于摧毁连接城市 $5$ 和 $7$ 的道路后的总威胁；在这种情况下，威胁为 $(9 + 7)^2 + (1 + 4 + 2 + 6 + 4)^2 = 545$。