Imagine a planet with two beautiful islands. Each island is decorated with several cities, and they are connected by a network of bidirectional roads. The cost of traveling through each road is provided. Both the islands have equal number of cities and roads.

You are given two arrays, $A$ and $B$, where $A$ represents the beauty index associated with the cities on Island $1$, and $B$ represents the beauty index associated with the cities on Island $2$.

To journey from a city $i$ on Island $1$ to a city $j$ on Island $2$, there exists special unidirectional flights. However, specific conditions must be met:

• $j$ must be a multiple of $i$, indicating a compatible connection between the cities. (i.e. a unidirectional flight exists between city $i$ to city $j$ if and only if $j$ is a multiple of $i$)
• The cost of the flight is determined by multiplying the beauty indexes of $i^{\text{th}}$ city and $j^{\text{th}}$ city (i.e. $A[i]*b[j]$), ensuring a harmonious transition between the islands.

Your task is to calculate the minimum cost required to travel from city $x$ on Island $1$ to city $y$ on Island $2$. If it is not possible to travel from city $x$ to city $y$ based on the given conditions, you should output $-1$, indicating an incompatible connection.

Input format

• First line contains an integer $T$, the number of test cases.
• The first line of each test case contains 2 integers $N$, $M$ seperated by a space representing the number of cities and roads respectively.
• The next line contains $N$ integers space-seperated by a space representing the array $A$
• The next line contains $N$ integers space-seperated by a space representing the array $B$
• The next $M$ lines of each test case contains 3 space-seperated integers $X$, $Y$, $Z$ representing a bidirectional road from city $X$ of $1st$ island to city $Y$ of $1st$ island and it requires a cost $Z$ to travel through that road.
• The next $M$ lines of each test case contains 3 space-seperated integers $X$, $Y$, $Z$ representing a bidirectional road from city $X$ of $2nd$ island to city $Y$ of $2nd$ island and it requires a cost $Z$ to travel through that road.
• The next line of each test case contains 2 space-seperated integers $x$, $y$ which are described in the problem statement.
• It is guaranteed that there are no self loops or multiple edges in the graphs.

Output format

For each testcase, output an integer, the minimum cost required to travel from city $x$ in $1st$ island to city $y$ in $2nd$ island. Or print $-1$ if it's an incompatible connection in a new line.

Constraints

• $1 \leq T \leq 2*10^5$
• $3 \leq N \leq 4*10^5$
• $1 \leq M \leq 4*10^5$
• $1 \leq A[i] \leq 10^9$
• $1 \leq B[i] \leq 10^9$
• $1 \leq X, Y \leq N, 1 \leq Z \leq 10^9$
• $1 \leq x, y \leq N$
• Also it's guaranteed that the sum of  $N$, $M$ over all test cases doesn't exceed $4*10^5$