Skills Assessment

In a company, there are ~N~ employees. Each employee has a supervisor, except for the company's director, who has no one above them. The company's organizational chart, which is a diagram showing who is the supervisor of whom, resembles a tree structure with the director at the root.

For each employee ~A~, we define the "supervisory group" as follows:

• Employee ~A~ belongs to their own supervisory group and
• for each subordinate ~B~ of employee ~A~, all members of ~B~'s supervisory group also belong to ~A~'s supervisory group.

This year, the company decided to conduct a skills assessment of its employees by having them take an ability test. Each employee received a score ranging from ~1~ to ~T~.

We aim to answer questions such as: "How many employees in the supervisory group of ~A~ scored between ~L~ and ~U~ (inclusive)?"

To further complicate matters, some employees decided to retake the test, resulting in changes to their scores...

Input:

The first line of the input will contain three natural numbers ~N~, ~T~ and ~Q~: the number of employees, the maximum score value, and the number of actions your program needs to perform.

The next ~N~ lines describe the employees, numbered from ~1~ to ~N~. Specifically, the ~i~-th line contains two integers ~P_i~ and ~S_i~, separated by a space. This means that employee ~i~ reports to employee ~P_i~ and scored ~S_i~ in the test. For the company director, who has no supervisor, ~P_i = 0~. Assume that the company's organizational chart defined in these lines is always valid.

The next ~Q~ lines describe an action your program should execute. Actions are of two types, starting either with the letter "~u~" or "~q~", followed by two or three integers respectively, separated by spaces The meaning of the actions is as follows:

• u ~A_j~ ~S_j~ (update) Employee ~A_j~ has retaken the test and scored ~S_j~.
• q ~A_j~ ~L_j~ ~U_j~ (query) Answer the question: How many employees in the group supervised by employee ~A_j~. have scored ~S~ such that ~L_j \le S \le U_j~.

Output:

The output should contain one line for each action of type "~q~" (query). Each of these lines should contain, in order, an integer: the answer to the corresponding query.

Constraints:

• ~1 \le N \le 40.000~.
• ~1 \le T \le 40.000~.
• ~1 \le Q \le 40.000~.
• Time Limit: ~1~ sec.
• Memory Limit: ~256~ MB.
• For test cases with a total value of ~30%~, it will be ~N \le 1.000~, ~Q \le 1.000~.
• For test cases with a total value of ~20%~, it will be ~T = 1~, i.e. all employees will have received the same score, and the only thing needed is to count them.
• For test cases with a total value of ~20%~, it will be ~T = 10~.

Example of Input - Ouput:

input:

4 4 3
0 1
1 2
1 4
2 3
q 1 2 3
u 4 1
q 2 2 3

output:

2
1

Explanation of the example:

The first question has an answer of ~2~ because in the group supervised by ~1~, there are two employees with scores between ~2~ and ~3~ (employee ~2~ has a score of ~2~ and employee ~4~ has a score of ~3~). Then, the score of ~4~ changes to ~1~. The second question now has an answer of ~1~ because in the group supervised by ~2~, there is now only one employee with a score between ~2~ and ~3~ (employee ~2~ himself, who has a score of ~2~).