给定一棵包含 $n$ 个节点的树。每个节点都有一个非负整数权值 $v_i$。

树上每条路径（从顶点 $i$ 到顶点 $j$）都有一个与值 $A_{ij}$，即路径上所有节点权值的按位与（bitwise-and）。类似地，每条路径都有一个或值 $O_{ij}$ 和一个异或值 $X_{ij}$，分别对应路径上所有节点权值的按位或（bitwise-or）和按位异或（bitwise-xor）。

计算以下三个值： $$\sum_{i,j} A_{ij}^2, \quad \sum_{i,j} O_{ij}^2, \quad \sum_{i,j} X_{ij}^2$$ 其中求和范围覆盖树上所有的 $n^2$ 条路径。

由于答案可能很大，请将每个求和结果对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的节点数。

第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ ($0 \le v < 2^{25}$)，表示树中每个节点的权值。

接下来的 $n-1$ 行，每行包含两个整数 $a_i, b_i$，表示边 $i$ 的两个端点。

输出格式

输出 3 个整数，分别表示所有路径的与值、或值和异或值的平方和。每个求和结果均需对 $998244353$ 取模。

样例

输入 1

2
14 2
2 1

输出 1

208 592 488

输入 2

5
3 9 14 7 12
4 1
4 3
4 5
3 2

输出 2

769 4627 1697

输入 3

12
10 3 8 13 6 2 3 14 1 5 10 6
10 1
6 2
2 10
9 7
2 9
9 11
3 7
8 2
5 7
4 7
12 2

输出 3

825 20705 12035