It is vacation time and the citizens of virtualBit are visiting their relatives. There are N cities in virtualBit. There are some roads connecting these cities in such a way that there is one and only one unique path between any pair of these cities. Each city sells only one type of gift with a fixed price V_i.

There are Q citizens who wish to visit their relatives. The i^th citizen stays in city A_i and wants to visit his relative who lives in city B_i. They want to purchase some gifts for the children of their relatives. These gifts should be bought only from the cities that lie on the path from A_i to B_i (including the starting and ending points).

The children are very picky by nature. They love prime numbers and hence will only accept those gifts, whose cost is a prime number. Also, the children will only accept gifts that cost atleast L_i . But they also understand the financial constraints of their relatives and hence will not accept any gift that costs more than R_i.

Each citizen wants to know the number of cities from which he can buy gifts for the children of his relative. Please help him in finding the answer.

Input

The first line of the input contains two numbers N and Q, the number of cities and number of citizens respectively.

The next line contains N numbers. The i^th number is the cost of gift being sold at city i.

The next N-1 lines contain two integers X and Y indicating that there is a bidirectional road between cities X and Y.

Each of the next Q lines contain a query of the form: A B L R.

Output

For i^th query, print the number of cities from which the i^th citizen can buy gifts while obeying the constraints on the cost of gifts.

Constraints

1<=N,Q<=10⁵

1<=V_i<=10⁶

1<=X, Y<=N

1<=A, B<=N

1<=L, R<=10⁶