SOLVE
LATER
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 i^{th} 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 i^{th} 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, i^{th} integer parent[i] denotes parent of (i + 1)^{th} numbered node.
The next line comprises N space separated integers :
The i^{th} integer B[i] denotes the index of the businessman who owns the factory numbered i.
The next line comprises M space separated integers:
The i^{th} integer threshold[i] denotes threshold money for i^{th} 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 * 10^{5}
1 <= M <= 5 * 10^{5}
1 <= Q <= 5 * 10^{5}
1 <= parent[i] <= i
1 <= B[i] <= M
1 <= threshold[i] <= 10^{18}
1 <= F <= N
1 <= X <= 10^{6}
0 <= D <= 10^{6}
For 15% tests, N,M,Q <= 2000
For 25% tests, D = 0
For rest, orignal constraints
Output Format :
Print M lines, where the i^{th} line denotes the year after which the i^{th} businessman earns his desired amount. If he doesn't earn it throughout the course of the Q years, print "rekt". (without quotes)
We have 3 factories, 2nd is dependent on 1st and 3rd is dependent on 2nd.
We have an information about 5 years. Let's see what's happening in first two years.
In 1st year 1st factory gets 2; 2nd factory is dependent on 1st and therefore gets 2+3; 3rd factory is dependent on 2nd, so it gets 2+3*2.
In 2nd year 2nd factory gets 2 and 3rd factory gets 2+3 because it depends on 2nd factory.