Prime Divisor on Tree Path

You are given a permutation of $P$ numbers which are $1$ to $P$ and a tree with $N$ nodes each node having a number written on it. Then you will be given $Q$ queries. In each query you will be given 4 numbers: $p_1$ $p_2$ $v_1$ $v_2$. You have to multiply all the numbers written on the nodes which are on the path from node $v_1$ and $v_2$, let the multiplication is $m$. Then you have to perform some steps. In each step, you have to:

1. choose any prime number $p$ which appears in the permutation from position $p_1$ to $p_2$ and can perfectly divide $m$.

2. update the value of $m$ by $m/p$.

The above step should be performed, until $m$ can’t be divided by any prime from the range $p_1$to $p_2$ in the permutation.

You have to count the number of required steps for each query.

Input

The first line contains three numbers $P$, $N$ and $Q$, denoting the size of the permutation, the number of nodes in the tree and the number of queries. $(1 \leq P \leq 10^6)$and $(1 \leq N, Q \leq 10^5)$

The next line contains $P$ integers, denoting a permutation of first $P$ integers ( $1$ to $P$).

The next line contains $N$ integers $x_i$, the $i^{th}$ number denotes the number written on the node $i$. $( 1 \leq x_i \leq 10^6)$

Each of the next $N-1$ lines contains two numbers $a$ and $b$, denoting there is an edge between the nodes $a$ and $b$. $(1 \leq a, b \leq N)$

Each of the next $Q$ lines contains four integers: $p_1$ $p_2$ $v_1$ $v_2$, denoting a query. $( 1 \leq p_1 \leq p_2 \leq P$ and $1 \leq v_1, v_2 \leq N)$

Output

For each query, print the required number of steps.

Sample

4 5 3
4 2 1 3
6 3 2 5 4
1 2
1 3
3 4
3 5
1 4 4 2
3 4 2 4
2 4 4 5

4
2
3