SALMAN - Salary Management

You are working as a software engineer of Moogle! Now the boss of Moogle wants you to create a program which will efficiently handle some operations. At first, we should tell you about the structure of the employees at Moogle! Each employee has an integer id from 1 to N. Where 1 is the id of the Managing Director of Moogle! , who is the greatest boss of all the employees. Then except the Managing Director, each employee has an immediate boss. No employees have more than one immediate boss. Now your boss wants to have some operation like this:

  1. He will give you an ID of an employee; you need to find the sum of salary of all the employees under that employee including him/herself.
  2. He will give you an ID of an employee; you need to increase the salary of all the employees under that employee including him/herself by the minimum of minimum salary of all the employees under that employee including him/her and 1000.

Let’s see the structure, hope you will get a clear idea about the problem.

Employee Hierarchy

Employee Hierarchy

Salary Table:

ID1234567
Salary (BDT)50030020010010200100


Now if your boss wants to do the first operation for Employee ID 2. Then the output will be: 300 + 100 + 200 = 600 BDT.

If your boss wants to do the second operation for the Employee ID 1, then the salary table becomes:

ID1234567
Salary (BDT)51031021011020210110


As minimum salary is 10 for Employee id 5 and which is less than 1000.

Input

Input starts with an integer T (≤ 3), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 105), q (1 ≤ q ≤ 50000) where N denotes the number of nodes and q denotes the number of queries. The nodes are numbered from 1 to N.

Then there will be N lines. The ith (1 ≤ i ≤ N) line contains two integers pi and si (0 ≤ pi ≤ N, 1 ≤ si < 500). pi denotes the parent and si denotes the salary of the ith employee, respectively. You can assume that the employee id with 1 is the managing director and only its parent is 0.

Each of the next q lines contains a query. Each query contains two integers: c and v (1 ≤ c ≤ 2, 1 ≤ v ≤ N), where c denotes operation type, and v denotes the employee id. If the c = 1, then it means to do the first operation. If c = 2, then the second operation.

You can assume that the input builds a valid rooted tree.

Output

For each case, print the case number in a line. Then for each query type 1, print the sum of the salary.

Example

Input:
1

7 3
0 500
1 300
1 200
1 100
3 10
2 200
2 100
1 2
2 1
1 2

Output:
Case 1:
600
630

Note

Dataset is huge. Use faster I/O methods.


Problem Setter: Ahmad Faiyaz

Special Thanks: Syed Shahriar Manjur


Added by:Faiyaz
Date:2013-12-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-11-27 18:34:23 Angel Gonzalez
DFS + Segment Tree + Lazy Propagation = AC
2014-05-11 00:40:03 Alex Abbas
KEEP MAKING WONDERFUL PROBLEMS LIKE THIS ONE!!!
2014-04-27 11:47:59 aristofanis
-------------- EDIT ----------------
Not using long long cost me many WA's...

Last edit: 2014-04-27 19:28:40
2014-09-23 18:35:43 Cosmin Rusu
Why Wa? I use Segment Tree with lazy update for sum....
L.E. Oups, looks like I had a HUGE bug in my code.
Nice problem :)

Last edit: 2014-03-07 15:55:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.