You live in a city that consists of \(N\) restaurants. Each restaurant has a unique index between \(1\) and \(N\) (both inclusive) and value denoted by the array \(V\) . A unique path exists between every pair of restaurants, which implies that each restaurant can be reached from every other restaurant. You are given an integer \(P\). Your task is to solve \(Q\) queries of the following form:  

\(A \ B\ L_1\  R_1\  L_2\  R_2\)

where \(A\) and \(B\) are the indices of two distinct restaurants and \(L_1\), \(R_1\), \(L_2\), and \(R_2\) are positive integers. For each query, determine the total number of ordered pairs of restaurants \((X,Y)\) such that the following conditions hold:

• \(X\) lies in the unique path between the restaurants \(A\) and \(B\)

• \(A\) lies in the unique path between the restaurants \(X\) and \(Y\)

• \(L_1 \le (V_X \% P) \le R_1 \)

• \(L_2 \le (V_Y \% P) \le R_2 \)

• \(A,\ B,\ X,\) and \(Y\) should be pairwise distinct

Input format

• First line: Three space-separated integers \(N\) , \(Q\), and \(P\) 
• Second line: \(N\) space-separated integers with \(i^{th}\) integer denoting \(V_{i}\) 
• Next \(N-1\) lines: Two space-separated integers \(U\) and \(V\) denoting a bidirectional path from restaurant \(U\) to \(V\) and vice versa
• Next \(Q\) lines: Six space-separated integers \(IN_{1}\), \(IN_{2}\), \(IN_3\), \(IN_4\), \(IN_5\), and \(IN_6\)describing one query. Let \(last\) denote the answer of the previous query (if its first query then \(last\) = 0). The parameters of the query can be calculated by the following conditions: 
  • \(A=IN_{1} \oplus last\)
  • \(B=IN_{2} \oplus last\)
  • \(L_1=IN_{3} \oplus last\)
  • \(R_1=IN_{4} \oplus last\)
  • \(L_2=IN_{5} \oplus last\)
  • \(R_2=IN_{6} \oplus last\)

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

Output format

For each query, print the answer on a separate line.

Constraints

\(2 \le N,Q \le 10^5\)

\(1 \le A, B \le N\) and \( A \ne B\)

\(1 \le L_1,R_1,L_2,R_2,P,V_{i} \le 10^{9}\)

\(L_1 \le R_1\ and\ L_2 \le R_2 \)

Subtasks

• For 10 points: \(2 \le N,Q \le 100\)
• For 20 points: \(2 \le N,Q \le 5000\)
• For 70 points: Original Constraints