题目描述

有 $n$ 个房间，每个房间 $i$ 有三个参数 $u_i,v_i$ 和 $w_i$。

维护 $q$ 组询问：

第 $i$ 组询问中，有一个颜色为 $c_i$，权值为 $0$ 的奶龙按编号顺序依次经过第 $l_i$ 到第 $r_i$ 个房间。

在它经过房间 $j$ 时，如果奶龙当前的颜色为 $u_j$，则它的颜色在它离开当前房间时变为 $v_j$，权值加上 $w_j$。

对于每组询问，求出奶龙在完成上述过程后的权值大小。

输入格式

第一行三个整数 $n$、$q$ 和 $o$，其中 $o$ 表示子任务编号。

接下来 $n$ 行每行三个整数 $u_i,v_i,w_i$。

接下来 $q$ 行每行三个整数 $c_i,l_i,r_i$。

输出格式

输出 $q$ 行，每行一个整数表示最终权值的大小。

样例输入

6 5 0

1 5 1

2 7 10

5 7 100

2 4 1000

7 4 10000

4 3 100000

5 1 6

1 2 5

2 3 6

1 1 4

4 3 6

样例输出

110100

0

101000

101

100000

大样例

见附件。对应每个子任务。

数据范围与约定

测试数据满足 $1\le n,q\le 10^6,1\le u_i,v_i,c_i\le 10^9,0\le \sum w_i\le 10^9,1\le l_i\le r_i\le n$。