时间限制：1秒　　内存限制：256M

---

【题目描述】

　　张雪机车在世界超级摩托车锦标赛获得三连冠，这激起了国人对摩托车越野赛的极大兴趣。
小H和朋友们最近一直在参见摩托车越野训练。赛道上有N个路标（1≤N≤105），按顺序依次标记为1,2,…,N，路标1为起点。
对于每个路标i>1，有一条从路标xi（1≤xi<i）出发的越野道直接到达路标i。这条越野道的难度为di（0≤di≤109），乐趣值为ei（0≤ei≤109）。
小H的M个朋友（1≤M≤105）每人会进行如下操作：选择一个终点路标i，然后从1出发骑行，直到抵达路标i。
每位朋友获得的乐趣值等于他们经过的所有越野道的乐趣值之和。每个朋友有不同的技能水平 s（0≤s≤109）和勇气值c（0≤c≤10），这限制他们选择的起始路标必须满足：骑行过程中最多有c条越野道的难度超过s。
请为每位朋友计算他们能获得的最大乐趣值。

【输入格式】

　　第一行包含N。
接下来2到N行，每行包含三个整数xi，di和ei，表示一条越野道从路标xi直达i。
随后一行包含M。
接下来 M行，每行包含两个整数s和c。

【输出格式】

　输出 M 行，每行对应一个朋友的答案。注意：可能需要使用 64 位整数类型。

【输入输出样例1】

　Input

4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0 

　Output

0
300
500
300
500
500
300
500

【输入输出样例2】

　Input

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

　Output

15
20
23
22
5
20

【数据限制】

测试点 1~4：N,M≤1000。
测试点 5~8：所有c=0。
测试点 9~20：无额外限制。

【来源】

　　Mr.he