题目描述

给一棵 $n(1 \le n \le 1000)$ 个节点的树，每个点有点权 $w_i(0 \le w_i < 2 ^ {15})$ 。

设 $f_x$ 表示树上有多少个连通块，满足点权异或和为 $x$ 。

求 $f_0, f_1, f2, ..., f{2 ^ {15} - 1}$ 对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个非负整数 $w_i$ 。

接下来 $n-1$ 行，每行两个正整数 $x, y$ ，表示树上存在边 $(x, y)$ 。

输出格式

输出一行，共 $2 ^ {15}$ 个非负整数，依次为 $f_0, f1, ..., f{2 ^ {15} - 1}$ 。

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 1000, 0 \le w_i < 2 ^ {15}$ 。