Animesh is the mayor of n00b_land - a city known for it's massive production of antidepressants.
The rise in demand for such medications have attracted M avaricious businessmen, conveniently numbered from 1 to M, from all around the world. There are N factories in n00b_land - and each factory is owned by one of the M businessmen. Again, the factories are conveniently numbered from 1 to N. Moreover, some factories are dependent on other smaller factories to obtain their raw material. There are N - 1 dependencies in total. Factory numbered 1 is main factory and is not dependent on any other factory. For each factory numbered from 2 to N, it depends on exactly one other factory which has strictly lower index than it.
In other words, the network of dependencies between factories form a tree rooted at 1.
Every year, some factory F earns an amount X as donation from the generous people of pr0_land. The pr0 people of pr0_land ask the factory to distribute wealth in the following manner :
1) Add X to F.
2) Add X + D to all factories which are dependent on F.
3) Add X + 2*D to all factories which are dependent on any factory from step (2).
In general, add X + (K) * D to a factory G if there are K dependencies en-route from F to G.
The businessmen in n00b_land do not care about the welfare of the workers in the factories. As a
result, they take all the money that a factory receives by donation from the pr0 people of pr0land.
Further, each businessman has a value Threshold(i), denoting the amount the ith businessman wants to earn.
Given the reports for Q consecutive years (Years are numbered 1..Q), your task is to find the year after which the ith businessman would have earned atleast Threshold(i).
Input Format :
The first line of input comprises space separated integers N and M.
The second line consists of N - 1 space separated integers . Here, ith integer parent[i] denotes parent of (i + 1)th numbered node.
The next line comprises N space separated integers :
The ith integer B[i] denotes the index of the businessman who owns the factory numbered i.
The next line comprises M space separated integers:
The ith integer threshold[i] denotes threshold money for ith businessman
The next line of input comprises one integer Q.
The next Q lines comprises three integers (F, X, D) each.
Constraints :
1 <= N <= 5 * 105
1 <= M <= 5 * 105
1 <= Q <= 5 * 105
1 <= parent[i] <= i
1 <= B[i] <= M
1 <= threshold[i] <= 1018
1 <= F <= N
1 <= X <= 106
0 <= D <= 106
For 15% tests, N,M,Q <= 2000
For 25% tests, D = 0
For rest, orignal constraints
Output Format :
Print M lines, where the ith line denotes the year after which the ith businessman earns his desired amount. If he doesn't earn it throughout the course of the Q years, print "rekt". (without quotes)