Anchal lives in a city which has \(N\)​ ice cream parlours. The city has \(N-1\) connections such that every ice cream parlour can be reached from every other ice cream parlour. Each parlour has only one type of ice cream with cost \(C_{i}\)​ for each \(1 \le i \le N\)​. Anchal has \(Q\)​ queries with each query specifying a city \(R\)​ and two integers \(X\) and \(Y\). In every query she wants to reach the same destination ice cream parlour \(D\).Anchal wants to calculate the number of cities from which she can start her journey and reach the destination city \(D\)​ along the shortest path between the source and the destination city such that city \(R\) lies in its path and the sum of ice creams for these three cities lie between \(X\)​ and \(Y\) (Both inclusive).

Note : City \(D\) , City \(R\) and the city from which Anchal starts are pairwise distinct.

INPUT FORMAT

• First line consists of three space separated integers \(N\) , \(Q\) and \(D\) as described above 
• Second line consists of \(N\) space separated integers with \(i^{th}\) integer denoting \(C_{i}\) as described above
• Next \(N-1\) lines each consist of 2 space separated integers \(U\) and \(V\) denoting there is a bidirectional path from ice cream parlour \(U\) to \(V\) and vice versa
• Each of the following \(Q\) lines contain three space separated integers \(IN_{1}\) , \(IN_{2}\) and \(IN_{3}\)  describing one query. Lets define \(last\) as the answer of the previous query (If its first query then \(last\) = 0). The parameters of the query can be calculated by : 
  • \(R=IN_{1} \oplus last\)
  • \(X=IN_{2} \oplus last\)
  • \(Y=IN_{3} \oplus last\)

where \({\oplus}\) is the symbol for logical XOR.

OUTPUT FORMAT

• For each query, print the answer to it on a separate line

CONSTRAINTS

• \(1 \le N,Q \le 10^5\)
• \(1 \le D, R \le N\) and \(R \ne D\)
• \(1 \le X,Y,C_{i} \le 10^{12}\)
• \(X \le Y\)

SUBTASKS

• For 10 Points : \(1 \le N,Q \le 100\)
• For 20 Points : \(1 \le N,Q \le 1000\)
• For 70 Points : Original Constraints