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$$$.
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 $$$3$$$ integers — the sum of squares of all and-values, or-values, and xor-values respectively. Each sum should be reported modulo $$$998244353$$$.
2 14 2 2 1
208 592 488
5 3 9 14 7 12 4 1 4 3 4 5 3 2
769 4627 1697
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
825 20705 12035
| Name |
|---|


