You are working for IPSCorp, a multinational corporation which is revolutionizing the world by providing end-to-end solutions for high-impact paradigm shifts. This important task requires that key players touch base with industry leaders to incentivize core competencies and faciliate organic growth.
As you can probably guess from this description, most of IPSCorp consists of layers and layers of incompetent managers. Since they need to look productive, they spend their workdays attending endless meetings and sending pointless memos to their subordinates. Making business decisions is hard, so the memos are always about trivial issues such as the office dress code.
When a manager writes a memo, he only sends it to his direct reports (i.e. subordinates of which he is the direct supervisor). They read the memo and forward it to their own direct reports. This way, the memo goes deeper and deeper in the company hierarchy. But after the memo has been forwarded a certain number of times, the recipients will just ignore it, hoping that the original author won’t notice. This depends on the memo’s general tone, number of exclamation marks, firing threats, and so on. We call the maximum number of forwards the “importance level”.
A memo of importance level 0 (“I think we should wear red ties.”) only affects the memo’s author – he starts wearing a red tie, but even his direct reports ignore it. A memo of importance level 1 (“I want everyone in this room to wear blue ties from now on.”) affects the author and his direct reports, but nobody else cares. A memo of importance level 2 (“New department policy: only green ties allowed!”) also affects the direct reports of the author’s direct reports. And so on.
IPSCorp consists of n employees, labeled from 1 to n and organized in a hierarchical tree. All employees own ties of c colors labeled from 1 to c.
At the beginning, everyone is wearing a tie of color 1. Then, q events happen. Events are of two types: Either a given person writes a memo of a given importance level, and its recipients (including the person who wrote it) start wearing ties of a given color, or we want to know what tie a given employee is wearing at the moment.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Every test case starts with a line containing the integers n, c and q. The next line contains n − 1 integers named s2 to sn, where si is the supervisor of employee i (1 ≤ si < i). Employee 1 is the company president and has no supervisor.
The i-th of the following q lines contains three integers ai, li, ci describing event i (1 ≤ ai ≤ n; 0 ≤ li ≤ n; 0 ≤ ci ≤ c). If ci is nonzero, it means person ai sent a memo of importance level li saying the new tie color is ci. If ci is zero, then li is also zero, and it means you have to find the tie color worn by person ai.
In the easy subproblem G1, 1 ≤ n, c, q ≤ 10 000.
In the hard subproblem G2, 1 ≤ n, c, q ≤ 1 000 000. Because the input file size for subproblem G2 is about 100 MB, you cannot download it directly. Instead, we have provided a small Python 2 program that will generate the file g2.in when executed.
For each test case: Let yi be equal to 0 if ci is nonzero, or the tie color you found in event i if ci is zero. Then, let zi be i ⋅ yi. Output one line with a single number: the sum of z1 + … + zq modulo 109 + 7.
Input:
1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0Output:
32At the beginning, everyone has tie color 1 (including employee 3). Then, employees 2, 3 and 4 change to color 3. Employee 1 then changes to color 2, but because his memo had importance level 0, everyone else stays unchanged. Finally, employee 4 changes his color back to 1. His direct reports would change too, but he doesn’t have any. Together, we get 1 ⋅ 1 + 2 ⋅ 0 + 3 ⋅ 3 + 4 ⋅ 0 + 5 ⋅ 3 + 6 ⋅ 0 + 7 ⋅ 1 = 32.