Xiao C and Xiao G often study game theory problems together. One day, they came up with the following game:

There is an undirected graph with $n$ vertices and $m$ edges. Initially, each vertex has a color, either black or white. Now, for each edge, they must make a choice: either invert the colors of the two vertices connected by this edge (black becomes white, white becomes black), or do nothing. They want to turn all vertices white. They want to know how many of the $2^m$ possible decision combinations can achieve this goal.

Xiao G thinks this problem is too simple, so he also wants to know, for each vertex $i$, what the new answer would be if that vertex and all edges connected to it were removed.

Since the answer can be very large, you only need to output the result modulo $10^9 + 7$.

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, representing the number of vertices and edges.

The next $m$ lines each contain two integers $u, v$, describing an edge in the undirected graph.

The next line contains a binary string of length $n$. If the $i$-th character is $0$, the $i$-th vertex is white; otherwise, it is black.

Output

For each test case, output a single line containing $n+1$ integers. The first integer represents the answer when no vertices are removed. The following $n$ integers represent the answers when the $i$-th vertex is removed, respectively.

Examples

Input 1

2
5 5
1 2
2 3
3 4
2 4
3 5
00000
5 4
1 2
2 3
2 4
2 5
11111

Output 1

2 2 1 1 1 2
0 1 0 1 1 1

Note

For the first test case, when no vertices are removed, there are two solutions: either perform no operations on any edges, or perform operations on edges $(2, 3), (3, 4), (2, 4)$.

When vertex 2, 3, or 4 is removed, the only solution is to perform no operations on any edges. Note that the graph may not be connected.

Input 2

See game/game2.in and game/game2.ans in the contestant directory.

Output 2

See game/game2.in and game/game2.ans in the contestant directory.

Constraints

For all data, $1 \le T \le 5$, $1 \le n, m \le 10^5$, $1 \le u, v \le n$. There are no multiple edges or self-loops.