Bribery

ZJiaQ is a solider. In his army,every solider have a boss who is also a solider . Now, AFA want to bribe some solider to attack ZJiaQ .Every solider have a ID, and evry day ,they will get a new ID.ZJiaQ want to avoid been attacked. The only way is that he bribe the boss of the solider or the boss of the boss of the solider or...
Once he bribe a boss ,the boss can stop one solider who is branch of him.In this army,everybody only can send money to his boss,if ZJiaQ want to send money to the boss of his boss.The money should pass through his boss and his boss will get 1 coin.
Now ZJiaQ want to know how much will he cost.

There are multiply test case . For each case , first line contains a integer n (3 < = n < = 40000) the number of node is from 0 to n-1. next line contains n integers a0,a2…an-1 ( 1<= ai <= 100000 ) . Ai is the money of bribery for the solider whose ID is i . next line contains n-1 integers f1, f2 …fn-1 ( 0 <= fi < n ) . fi is the boss of solider i. next line contains a integer m (1<= m<=40000). Next q lines contain 3 integers l ,r ,p (0 < l < = r < n,p < l or p>r),l,r means that AFA bribe soliders whose Id are between l and r.p is ZJiaQ's ID Now.

Output the Ans mod 10000007 of each query.

3
2 2 2
0 0
2
1 1 2
2 2 1


10
52 30 56 13 98 53 75 80 7 34
3 0 0 3 2 2 9 1 0
5
2 9 1
5 5 8
2 2 1
2 6 7
2 7 1

2
2


331
54
53
265
278

BestCoder Round #50 (div.1) ($)