Byteasar has a tree $T$ with $n$ vertices conveniently labeled with $1,2,...,n$. Each vertex of the tree has an integer value $v_i$.
The value of a non-empty tree $T$ is equal to $v_1\oplus v_2\oplus ...\oplus v_n$, where $\oplus$ denotes bitwise-xor.
Now for every integer $k$ from $[0,m)$, please calculate the number of non-empty subtree of $T$ which value are equal to $k$.
A subtree of $T$ is a subgraph of $T$ that is also a tree.
Input
The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, the first line of the input contains two integers $n(n\leq 1000)$ and $m(1\leq m\leq 2^{10})$, denoting the size of the tree $T$ and the upper-bound of $v$.
The second line of the input contains $n$ integers $v_1,v_2,v_3,...,v_n(0\leq v_i < m)$, denoting the value of each node.
Each of the following $n-1$ lines contains two integers $a_i,b_i$, denoting an edge between vertices $a_i$ and $b_i(1\leq a_i,b_i\leq n)$.
It is guaranteed that $m$ can be represent as $2^k$, where $k$ is a non-negative integer.
Output
For each test case, print a line with $m$ integers, the $i$-th number denotes the number of non-empty subtree of $T$ which value are equal to $i$.
The answer is huge, so please module $10^9+7$.
