A. And Xor Tree
time limit per test
10 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes. Each node has a non-negative integer value $$$v_i$$$.

Each path (from vertex $$$i$$$ to vertex $$$j$$$) on the tree has an and-value $$$A_{ij}$$$ which is the bitwise-and of the values of all nodes on the path. Similarly, each path has an or-value $$$O_{ij}$$$ and an xor-value $$$X_{ij}$$$ corresponding to the bitwise-or and bitwise-xor of the values of the nodes on the path respectively.

Compute the following three values: $$$$$$\sum_{i,j} A_{ij}^2, \sum_{i,j} O_{ij}^2, \sum_{i,j} X_{ij}^2$$$$$$ where each sum ranges over all $$$n^2$$$ paths on the tree.

As the answers may be large, report each sum modulo $$$998244353$$$.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of nodes in the tree.

The second line of input contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$0 \leq v \lt 2^{25}$$$) — the value of each node in the tree.

The following $$$n - 1$$$ lines each contain two integers $$$a_i, b_i$$$ — the endpoints of edge $$$i$$$.

Output

Output $$$3$$$ integers — the sum of squares of all and-values, or-values, and xor-values respectively. Each sum should be reported modulo $$$998244353$$$.

Examples
Input
2
14 2
2 1
Output
208 592 488
Input
5
3 9 14 7 12
4 1
4 3
4 5
3 2
Output
769 4627 1697
Input
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
Output
825 20705 12035