Description

Kazami Yuuka has a good friend named Yakumo Yukari. They often watch the stars and the moon together, chatting from poetry and songs to life philosophy. Recently, they had a sudden idea to open a small shop in Gensokyo to do business and make some money.

This idea is certainly great, but they also found a problem: where to open the shop and which group of customers to target. Interestingly, the map of Gensokyo is a tree. There are $n$ places in total, numbered from $1$ to $n$, connected by $n-1$ weighted edges. Each place is inhabited by a youkai, and the age of the youkai at place $i$ is $x_i$.

Youkai are relatively quiet, so they do not want to be adjacent to too many youkai. Therefore, the degree of every vertex in this tree is at most $3$. Interests change naturally with age. For example, our $18$-year-old girls Yuuka and Yukari may prefer cute things. Yuuka discovered through research that a youkai’s interests basically depend only on age. So Yuuka plans to choose a place $u$ (a vertex id), and open a shop at $u$ targeting youkai whose ages are between $L$ and $R$ (that is, ages greater than or equal to $L$ and less than or equal to $R$).

It is possible that place $u$ is far from these youkai. Thus, Yuuka wants to know the sum of distances from all youkai with ages in $[L, R]$ to $u$ (the distance from a youkai to $u$ is the sum of edge weights along the path from its place to $u$). Yuuka calls this the convenience value of the shop plan.

They have not yet decided where to open the shop, and Yukari has prepared many plans. For each plan, what is the convenience value?

Input Format

• The first line contains three space-separated integers $n$, $Q$, and $A$, representing the size of the tree, the number of shop plans (queries), and the upper bound of youkai ages.
• The second line contains $n$ space-separated integers $x_1, x_2, \ldots, x_n$. Here $x_i$ is the age of the youkai at place $i$, satisfying $0 \le x_i \lt A$. (Age can be $0$, for example, a newborn youkai has age $0$.)
• The next $n-1$ lines each contain three space-separated integers $a$, $b$, and $c$, indicating that there is an edge of weight $c$ ($1 \le c \le 1000$) between vertices $a$ and $b$, where $a$ and $b$ are vertex ids.
• The next $Q$ lines each contain three space-separated integers $u$, $a$, and $b$.

For each of these $Q$ lines, compute $L$ and $R$ from $a$, $b$, and $A$. This specifies the query “open a shop at place $u$, targeting youkai with ages in $[L, R]$, and ask for the convenience value.”

• For the first query (the $1$-st line), compute: $L=\min(a \bmod A, b \bmod A)$, $R=\max(a \bmod A, b \bmod A)$.
• For the $2$-nd to the $Q$-th queries, suppose the convenience value obtained from the previous query is $ans$. Then compute: $L=\min((a+ans) \bmod A, (b+ans) \bmod A)$, $R=\max((a+ans) \bmod A, (b+ans) \bmod A)$.

Output Format

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

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

1603 
957 
7161 
9466 
3232 
5223 
1879 
1669 
1282 
0

Hint

Constraints: $n \le 1.5 \times 10^5$, $Q \le 2 \times 10^5$. For all testdata, $A \le 10^9$.

Translated by ChatGPT 5