题目背景

本题征求时间复杂度低于 $O(n^2)$ 的做法，若有人成功，请联系题目提供者。

数据生成器在附件，运行前需要先将 std.cpp 编译为名为 std 的可执行文件。

公元前 278 年的今天，伟大的诗人屈原投汨罗江自尽，距今已有 2303 年。

有一颗江边的树想要纪念他，所以请你来对这棵树做一些装饰。

题目描述

有一个 $n$ 个点的树，点的编号从 $1$ 到 $n$。

第 $i$ 个点的点权是 $a_i$。

定义 $f(x,y) = x \land (x \oplus y)$。

定义 $all(i)$ 为点 $i$ 的所有能通过一条边到达的点的集合。

定义如下操作：

先选定一个点 $i$，以及一个其直接连接的点集 $s \subseteq all(i)$。
然后，收益加上 $\sum\limits_{v\in s}f(a_i,a_v) - \sum\limits_{v\in all(i)}(a_v\land a_i)$。
然后，$a_i \leftarrow 0$。

定义树的价值为对其执行任意次以上操作能获得的最大收益（假设一开始收益为 $0$，上述操作仅用于定义树的价值，不会真的执行）。

定义森林的价值为其中所有树的价值的总和减去附加代价，森林中的两个点属于同一棵树，当且仅当两个点之间存在一条路径连接。

一开始，附加代价等于 $0$。

你可以执行以下两种操作，其中第一种操作次数没有限制，第二种操作最多执行 $k$ 次：

1. 选定两个点 $u,v$，使得 $u,v$ 之间有直接连边，令 $x=a_u,y=a_v$，附加代价减去 $x+y$，然后将 $u,v$ 之间的边断开。
2. 选定一个点 $u$，将 $u$ 点删除，并断开 $u$ 连接的所有边。

答案为经过上述操作之后，题目给定的树形成的森林的最小价值。

你需要对于 $k \in [0,lim]$ 都计算出这个答案。

注释一：$a \land b$ 的意思是 $a$ 和 $b$ 的按位与值。

注释二：$a \oplus b$ 的意思是 $a$ 和 $b$ 的按位异或值。

注释三：$a \leftarrow 0$ 的意思是将 $a$ 赋值为 $0$。

输入格式

第一行两个以空格分开的整数，分别是 $n$ 和 $lim$。

第二行共 $n$ 个以空格分开的整数，代表 $a_1,a_2,\cdots,a_n$。

接下来 $n-1$ 行，每行两个以空格分开的整数 $u,v$，代表 $u,v$ 之间存在一条边。

输出格式

输出一行 $lim+1$ 个由空格隔开的整数，分别代表 $k=0,1,2,\cdots,lim$ 的答案。

5 3
1 4 5 1 4
1 2
2 3
3 4
4 5

15 6 0 0 

提示

对于 C++ 语言，答案可能会超过 long long 范围，请使用 128 位整型，或者其他高精度。

对于全部的数据：$0 \le lim \le n \le 2000$，$\forall i \in [1,n],0 \le a_i \le 2^{63}-1$，详细数据范围见下表。
| Subtask 编号 | 特殊限制 | 分值 | | :----------: | :--------------: | :----:| | #1 | $lim=0,n\le 10$ | $10$ | | #2 | $lim=0,n \le 20$ | $15$ | | #3 | $lim=0$ | $20$ | | #4 | $n\le 6$ | $15$ | | #5 | $n \le 100$ | $30$ | | #6 | 无 | $10$ |