In DMOJ forest, there is a tree with $N$ nodes, conveniently numbered from $1$ to $N$, connected by $N-1$ weighted edges. The $i^{\text{th}}$ edge connects nodes $u_i$ and $v_i$ with distance $w_i$. On each node, a monkey lives there. The monkey at node $i$ has a ranking $r_i$. Multiple monkeys may have the same ranking.

Monkey king plans to host a banana eating competition. He picks up a node $X$ as the location and invites monkeys whose rankings are within $[L,R]$ (i.e. $L\le r_i\le R$) to attend this event. Monkey king wants to figure out the sum of distances for all invited monkeys travelling to $X$. Since monkey king hasn't found out the best location, he will ask you $Q$ queries. In the $i^{\text{th}}$ query, he will give you $X_i$, $L_i$ and $R_i$. You need to tell him the sum of distances for monkeys with rankings in $[L_i,R_i]$ travelling to $X_i$. Because monkey king is quite impatient, you must answer his queries online.

Constraints

For all subtasks:

$1\le N\le 150000$

$1\le Q\le 200000$

$1\le M\le {10}^9$

Subtask	Points	Additional constraints
$1$	$19$	$N\le 3000$, $Q\le 300$, $M\le {10}^9$
$2$	$21$	$N\le {10}^5$, $Q\le {10}^5$, $M\le 20$
$3$	$23$	$N\le {10}^5$, $Q\le {10}^5$, $M\le {10}^9$
$4$	$37$	No additional constraints.

Input Specification

The first line contains three integers, $N$, $Q$, and $M$ ($1\le N\le 150000$, $1\le Q\le 200000$, $1\le M\le {10}^9$), where $N$ is the number of nodes in the tree, $Q$ is the number of queries, and $M$ is used to decode each query.

The second line contains $N$ integers, $r_i$, ($0\le r_i<M$), the ranking of the $i^{\text{th}}$ monkey.

Each of the following $N-1$ lines contains three integers, $u_i$, $v_i$ and $w_i$, ($1\le u_i,v_i\le N$, $1\le w_i\le 1000$), an edge between nodes $u_i$ and $v_i$ with length $w_i$.

$Q$ lines of input follow. The $i^{\text{th}}$ line contains three integers, $X_i$, $l_i$ and $r_i$, where $l_i$ and $r_i$ are the encoded ranking interval. You can get the actual $L_i$ and $R_i$ by calculating $L_i=min((l_i+\text{lastans})\mathrm{\%}M,(r_i+\text{lastans})\mathrm{\%}M)$ and $R_i=max((l_i+\text{lastans})\mathrm{\%}M,(r_i+\text{lastans})\mathrm{\%}M)$, where $\text{lastans}$ is the answer for the previous query, and specially $\text{lastans}=0$ for the first query.

Output Specification

Print $Q$ lines. The $i^{\text{th}}$ line contains an integer, the sum of distances for the $i^{\text{th}}$ query.

Sample Input

10 5 10
0 0 7 2 1 4 7 7 7 9
1 2 5
2 3 3
1 4 4
2 5 6
4 6 5
3 7 2
1 8 7
6 9 3
7 10 4
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7

Sample Output

21
75
61
117
68