Alice and Bob are playing a coloring game. The game is played on a connected graph with $N$ vertices and $M$ ($N-1 \le M \le N$) edges. Bob wants to surround Alice, while Alice wants to escape Bob's encirclement.

At the start of the game, Alice colors vertex 1 black to indicate she occupies it, and Bob colors all vertices in the set $S$ white to indicate he occupies these $|S|$ vertices. It is guaranteed that 1 is not in $S$. The two players then take turns, with Alice moving first. In each turn, the current player can choose a vertex adjacent to one they already occupy (a black vertex for Alice, a white vertex for Bob) that has not yet been colored, occupy it, and color it with their own color. If there are no available vertices to color, the player must skip their turn. The game ends when all vertices have been colored.

Alice and Bob have agreed on a non-empty set of vertices $T$ in the graph. If all vertices in $T$ are colored white when the game ends, Bob has successfully surrounded Alice and wins. Otherwise, there must exist at least one vertex in $T$ that is colored black, in which case Alice wins. Note that $T$ may contain vertices from $S$ and vertex 1.

Both Alice and Bob play with optimal strategies. Bob notices that in some situations, Alice has a significant advantage, and the game would be more playable if Alice were to skip some of her turns to create a fairer situation. Bob wants to know the minimum $k$ such that if Alice skips her first $k$ turns, he can win. Alice only skips her first $k$ turns and plays optimally in the remaining turns; this is equivalent to saying Bob takes $k$ extra turns before Alice's first move. Note that if Bob has no legal moves during a turn that Alice skips, Bob must still skip his turn according to the rules. If Bob wins on the original graph, output 0. If Bob cannot win even when $k = 1000000$, output 1000000.

Since the graph can be very large, it is generated as follows: First, generate an empty graph with $n$ vertices labeled 1 to $n$. Next, add $m$ chains. The $i$-th chain is denoted as $(u_i, v_i, l_i)$, where $1 \le u_i, v_i \le n$ and $u_i \neq v_i$. First, add $l_i$ vertices, denoted as $x^i_1, x^i_2, \dots, x^i_{l_i}$. Then, add undirected edges between $(u_i, x^i_1), (x^i_1, x^i_2), (x^i_2, x^i_3), \dots, (x^i_{l_i-1}, x^i_{l_i}), (x^i_{l_i}, v_i)$. * After this operation, the $l_i$ newly added vertices in this round will not be connected to any other vertices; that is, the $x^i_1 \dots x^i_{l_i}$ in different chains are all distinct vertices. Specifically, if $l_i = 0$, no new vertices are added, and an undirected edge is added directly between $(u_i, v_i)$.

It is guaranteed that all vertices in sets $S$ and $T$ are among the $n$ vertices generated initially.

Input

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

For each test case: The first line contains four integers $n, m, |S|, |T|$ ($1 \le |S| \le n-1, 1 \le |T| \le n, n-1 \le m \le n$). The next $m$ lines each contain three non-negative integers $u_i, v_i, l_i$ ($1 \le u_i, v_i \le n, 0 \le l_i \le 10^6$), representing the $i$-th chain. The next line contains $|S|$ integers $s_1 \dots s_{|S|}$ representing all elements in set $S$ ($2 \le s_i \le n$, no duplicates). The next line contains $|T|$ integers $t_1 \dots t_{|T|}$ representing all elements in set $T$ ($1 \le t_i \le n$, no duplicates).

It is guaranteed that $u_i \neq v_i$ (no self-loops), there are no identical $(u_i, v_i)$ pairs (no multiple edges), and the given graph is connected.

Output

Output $T$ lines. For each test case, output the minimum number of turns $k$ that Alice must skip for Bob to win. If Bob wins on the original graph, output 0. If Bob cannot win even when $k = 1000000$, output 1000000.

Examples

Input 1

5
6 5 2 2
1 2 0
2 3 0
2 4 0
3 5 0
4 6 0
5 6
3 4
6 5 2 2
1 2 1
2 3 0
2 4 0
3 5 0
4 6 0
5 6
3 4
5 4 2 2
1 2 1
1 3 1
2 4 0
3 5 0
4 5
2 3
8 8 1 2
1 2 2
2 3 1
3 4 0
4 5 0
5 6 0
6 7 0
7 2 1
5 8 0
8
3 7
8 8 1 2
1 2 3
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 2 0
5 8 0
8
3 7

Output 1

1
0
0
0
1

Examples 2

See the provided files.

Constraints

For 100% of the data, $m = n$ or $n-1$, $3 \le n \le 500$, $C = 10000$, $0 \le l_i \le 10^6$, $1 \le |S| \le n-1$, $1 \le |T| \le n$. It is guaranteed that there are no cycles in the graph with more than 100 vertices (counting only the first $n$ vertices). In each test case, at most 10 datasets satisfy $n > 50$, and at most 1000 datasets satisfy $n > 20$.