Prime Divisor on Tree Path

shahidul_brur Ada Lovelace National Gir...
Limits 1s, 512 MB

You are given a permutation of PP numbers which are 11 to PP and a tree with NN nodes each node having a number written on it. Then you will be given QQ queries. In each query you will be given 4 numbers: p1p_1 p2p_2 v1v_1 v2v_2. You have to multiply all the numbers written on the nodes which are on the path from node v1v_1 and v2v_2, let the multiplication is mm. Then you have to perform some steps. In each step, you have to:

  1. choose any prime number pp which appears in the permutation from position p1p_1 to p2p_2 and can perfectly divide mm.

  2. update the value of mm by m/pm/p.

The above step should be performed, until mm can’t be divided by any prime from the range p1p_1to p2p_2 in the permutation.

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

Input

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

The next line contains PP integers, denoting a permutation of first PP integers ( 11 to PP).

The next line contains NN integers xix_i, the ithi^{th} number denotes the number written on the node ii. (1xi106)( 1 \leq x_i \leq 10^6)

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

Each of the next QQ lines contains four integers: p1p_1 p2p_2 v1v_1 v2v_2, denoting a query. (1p1p2P( 1 \leq p_1 \leq p_2 \leq P and 1v1,v2N)1 \leq v_1, v_2 \leq N)

Output

For each query, print the required number of steps.

Sample

InputOutput
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

Submit

Login to submit.

Statistics

100% Solution Ratio
alifcsejuEarliest, 1M ago
alifcsejuFastest, 0.2s
alifcsejuLightest, 50 MB
alifcsejuShortest, 3213B
Toph uses cookies. By continuing you agree to our Cookie Policy.