make-n00b_land-great-again-circuits

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)

SAMPLE INPUT
3 3
1 2
1 2 3
10 15 20
5
1 2 3
2 2 3
3 5 10
1 4 0
1 3 3

SAMPLE OUTPUT
rekt
5
4

Explanation

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Bit manipulation

Sorting

Range queries

Segment trees revisited

Tree algorithms


Solutions: