问题 D: Distance on Tree

You are given a rooted tree with n nodes labeled from 1 to n, the root of which is the 1-st node, and the i-th node has a given value ai for each i = 1, 2, . . . , n. Given a parameter m and then q queries, the i-th of which is represented by two numbers xi and ki , your task is to maximize dis(u, v) + dis(v, w) + dis(w, u) by choosing three distinct nodes u, v and w in the subtree of xi such that au + av + aw ≡ ki (mod m). Here dis(u, v) is the length of the shortest path between the u-th and the v-th nodes on the tree. If there is no solution for a query, the answer is 0.

The first line contains three integers n, m (1 ≤ n, m ≤ 2 000) and q (1 ≤ q ≤ 2 × 105 ). The second line contain n integers a1, a2, . . . , an (0 ≤ ai < m). Following n − 1 lines describe the tree, each of which contains three integers u, v (1 ≤ u, v ≤ n) and w (1 ≤ w ≤ 2 × 105 ), representing an edge with length w between the u-th and the v-th nodes. In the following q lines, the i-th line contains two integers xi (1 ≤ xi ≤ n) and ki (0 ≤ ki < m), describing the i-th query. 

Output q lines, the i-th of which contains an integer, indicating the answer to the i-th query.

5 5 10
0 1 2 3 4
1 2 1
2 3 2
2 4 3
1 5 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4

12
14
16
16
20
0
10
0
0
0