You are given two short sequences of numbers, X and Y. Try to determine the minimum number of steps of transformation required to convert sequence X into sequence Y, or determine that such a conversion is impossible.

In every step of transformation of a sequence, you are allowed to replace exactly one occurrence of one of its elements by a sequence of 2 or 3 numbers inserted in its place, according to a rule specified in the input file.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line of input contains four integers - N, M, U, V (1 ≤ N, M ≤ 50). The next two lines of input contain sequences X and Y, consisting of N and M integers respectively. The next U lines contain three integers: a b c each, signifying that integer a can be converted to the sequence b c in one step of transformation. The next V-U lines contain four integers: a b c d each, signifying that integer a can be converted to the sequence b c d in one step of transformation. With the exception of N and M, all integers provided at input are positive and do not exceed 30.

The format of one set of input data is illustrated below.
N M U V
x₁ x₂ ... x_n
y₁ y₂ ... y_n
a₁ b₁ c₁
...
a_u b_u c_u
a_u+1 b_u+1 c_u+1 d_u+1
...
a_v b_v c_v d_v

Output

For each test case output -1 if it is impossible to convert sequence X into sequence Y, or the minimum number of steps required to achieve this conversion otherwise.

Example

Input:
1
3 10 2 3
2 3 1
2 1 1 2 2 1 2 1 2 1
3 1 2
3 3 3
3 1 3 2

Output:
6