Kazami Yuuka has a good friend named Yakumo Yukari. They often watch the stars and the moon together, discussing everything from poetry and literature to the philosophy of life. Recently, they had a sudden inspiration to open a small shop in Gensokyo to do some business and earn some money. This idea is certainly wonderful, but they also realized they are facing a problem: where should the shop be opened, and what kind of customers should it target?

Surprisingly, the map of Gensokyo is a tree structure. There are $n$ locations in Gensokyo, numbered from $1$ to $n$, connected by $n-1$ weighted edges. Each location is home to a monster, and the monster at the $i$-th location has an age of $x_i$. Monsters are creatures that prefer peace and quiet, so they do not wish to be adjacent to many other monsters. Therefore, the degree of every vertex in this tree is less than or equal to $3$. Like humans, monsters' interests change with age; for example, our 18-year-old girl Yuuka and Yukari prefer cute things. Through research, Yuuka found that a monster's interests are basically only related to its age. Therefore, Yuuka plans to choose a location $u$ (where $u$ is the location number) and open a shop at $u$ targeting monsters with ages between $L$ and $R$ (i.e., age $\ge L$ and age $\le R$). It is possible that location $u$ is quite far from these monsters, so Yuuka wants to know the sum of the distances from all monsters with ages between $L$ and $R$ to point $u$ (the distance from a monster to $u$ is the sum of the weights of the edges on the path from the monster's location to $u$). Yuuka calls this the "convenience value" of the shop opening plan. Yuuka and her friend have not yet decided where to open the shop, but Yukari has prepared many plans, so Yuuka wants to know the convenience value for each plan.

Input

The first line contains three space-separated integers $n$, $Q$, and $A$, representing the size of the tree, the number of shop opening plans, and the upper bound of the monsters' ages.

The second line contains $n$ space-separated integers $x_1, x_2, \dots, x_n$, where $x_i$ represents the age of the monster at the $i$-th location, satisfying $0 \le x_i < A$. (Ages can be $0$, for example, a newborn monster has an age of $0$.)

The next $n-1$ lines each contain three space-separated integers $a$, $b$, and $c$, representing an edge between vertex $a$ and $b$ with weight $c$ ($1 \le c \le 1000$), where $a$ and $b$ are vertex numbers.

The next $Q$ lines each contain three space-separated integers $u$, $a$, and $b$. For each of these $Q$ lines, use $a$, $b$, and $A$ to calculate $L$ and $R$, representing the query: "If we open a shop at location $u$, what is the convenience value for the age range $[L, R]$?"

For the first line, $L$ and $R$ are calculated as: $L = \min(a \pmod A, b \pmod A)$, $R = \max(a \pmod A, b \pmod A)$.

For the $2$-nd to $Q$-th lines, assuming the convenience value obtained from the previous line is $ans$, the $L$ and $R$ for the current line are calculated as: $L = \min((a + ans) \pmod A, (b + ans) \pmod A)$, $R = \max((a + ans) \pmod A, (b + ans) \pmod A)$.

Output

For each plan, output one line representing the convenience value.

Examples

Input 1

10 10 10
0 0 7 2 1 4 7 7 7 9 
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4

Output 1

1603
957
7161
9466
3232
5223
1879
1669
1282
0

Constraints

• For 20% of the data, $n, Q \le 3000$.
• For another 20% of the data, $n \le 100000, Q \le 100000$, and $A = 20$.
• For another 20% of the data, $n \le 100000, Q \le 100000$.
• For another 20% of the data, $n \le 150000, Q \le 150000$.
• For another 20% of the data, $n \le 150000, Q \le 200000$.
• For all data, $A \le 10^9$.