该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意：本题不考虑给定的 $a_i$，初始时所有点的点权均视为 0。选手仅需读入给定的 $a_i$ 并忽略其对答案的影响。

题目背景

戌蛤：然后这个的主要玩法是人物关系

我：但是我没有人物关系啊

戌蛤：就是你手里的牌之间关系越多分越多

戌蛤：太假了吧

我：这哪里假了啊

戌蛤：突然发现我也想不到什么

戌蛤：比如您和块 -> YNOI 大师

我：被您钦定为云南省选带师

戌蛤：有点好奇

戌蛤：我直接把卡牌介绍删了

戌蛤：会挂吗

我：我怎么知道（

戌蛤：整个人的 js 我读不太透

戌蛤：整 -> 这

题目描述

给出一棵无根树，点有点权，边有边权。初始时点权均为 $0$。

然后给出 $m$ 次操作，其中第 $i$ 次操作会给出两个非负整数 $x_i, k_i$，表示对于树上每个点 $p$，将 $a_p$ 累加上 $k_i \cdot \operatorname{dist}(x_i, p)$。其中 $\operatorname{dist}(u, v)$ 表示 $u$ 号点和 $v$ 号点之间唯一树上路径的边权和。

然后给出 $q$ 次询问，其中第 $i$ 次操作会给出三个正整数 $l_i, r_i, y_i$，表示询问在只保留第 $l_i$ 次操作到第 $r_i$ 次操作的情况下，$y_i$ 号点的点权是多少。询问互相独立，即每次询问结束后将树的形态恢复至初始。

输入输出格式

输入格式

输入数据的第一行包含三个正整数 $n, m, q$，分别表示树的节点数量，操作的数量和询问的数量。

输入数据的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。这 $n$ 个数没有任何作用，请忽略掉它们。

输入数据的接下来 $n - 1$ 行，第 $i$ 行包含三个非负整数 $u_i, v_i, w_i$，表示 $u_i$ 号点和 $v_i$ 号点之间有一条边，边权为 $w_i$。

输入数据的接下来 $m$ 行，第 $i$ 行包含两个非负整数 $x_i, k_i$，表示一次操作。

输入数据的接下来 $q$ 行，第 $i$ 行包含三个正整数 $l_i, r_i, y_i$，表示一次询问。

同一行内的多个数字之间由空格隔开。

输出格式

对于每次询问，输出一行一个整数表示答案。

输入输出样例

5 2 6
0 0 0 0 0
1 2 2
1 3 3
2 4 4
2 5 5
1 1
5 4
1 2 1
1 2 2
1 2 3
1 1 4
1 2 4
1 2 5

28
22
43
6
42
7

10 32 5
4 5 6 2 3 6 9 8 4 1 
1 2 3
2 3 3
2 4 3
2 7 1
3 5 2
5 6 10
5 8 3
7 9 2
9 10 0
4 8
6 10
3 1
10 7
6 7
8 0
9 5
8 3
4 3
8 10
8 9
10 9
8 4
3 0
5 9
6 1
1 6
3 0
3 9
6 9
1 7
10 1
5 9
8 8
4 1
10 2
2 7
1 7
6 2
6 2
2 1
6 2
15 30 3
16 20 4
14 25 10
18 23 9
15 26 10

409
270
550
330
550

样例解释

对于样例 #1，进行完第 $1$ 次操作后树的形态如下如所示

其中边旁边的蓝色数字表示边权，节点圈内的蓝色数字表示标号，节点旁边的红色数字表示边权。

进行完第 $2$ 次操作后树的形态如下如所示

数据范围与约定

$1 \leqslant n, m \leqslant 10^3$，$1 \leqslant q \leqslant 2 \times 10^6$。$0 \leqslant a_i, w_i, k_i \leqslant 10$，$1 \leqslant u_i, v_i, x_i, y_i \leqslant n$，$1 \leqslant l_i \leqslant r_i \leqslant m$。

时空限制：$\texttt{1s/256MiB}$。

请 cin/cout 选手注意 IO 用时。

如果您秒了这道题，可以想一想 $n, m, q \leqslant 10^5$ 该怎么做。