Spy Network Intelligence Task Simulation

Nate Corporation is a vast intelligence organization with a huge spy network consisting of \(n\) spies. All spies are connected as a tree: there is exactly one head spy and each of the other \(n-1\) spies has exactly one direct superior. In this network, a spy can only communicate with his direct superior and immediate subordinates, and any two spies can exchange information through the network.

Every day, the company issues one of the following two tasks:

1. Collect Intelligence: Assign spy \(T\) to collect intelligence. Initially every spy is undercover with danger value \(0\). After a spy starts collecting intelligence on day \(d\), his danger value remains \(0\) on day \(d\) and increases by \(1\) on each subsequent day (i.e. on day \(d+1\) his danger becomes \(1\), on day \(d+2\) it becomes \(2\), and so on).
2. Pass Intelligence: Pass a piece of intelligence from spy \(X\) to spy \(Y\). Associated with the intelligence is a risk control value \(C\). The intelligence is transmitted along the unique simple path from \(X\) to \(Y\) in the tree. Any spy on this transmission path whose current danger value is greater than \(C\) is considered to be a threat to the operation.

For every task of the second type, you are to output two numbers: the total number of spies involved in the transmission and the number of spies among them that pose a threat (i.e. those with danger value greater than \(C\)).

Assume that the tasks are issued one per day (the first task occurs on day 1, the second on day 2, and so on), and that intelligence collection tasks only affect the danger value of a spy starting from the day after they begin collecting.

inputFormat

The input begins with an integer \(n\) (the number of spies). The next line contains \(n-1\) space-separated integers where the \(i\)th number (for \(i=2,3,\dots,n\)) denotes the direct superior (parent) of spy \(i\). It is guaranteed that spy 1 is the head spy and has no superior.

The next line contains an integer \(q\) indicating the number of tasks (days). Each of the following \(q\) lines describes a task in one of the two formats below:

• Collect Intelligence Task: 1 T — assign spy \(T\) to start collecting intelligence. If spy \(T\) has already started, this task has no effect.
• Pass Intelligence Task: 2 X Y C — pass intelligence from spy \(X\) to spy \(Y\) with risk control value \(C\). You must output the total number of spies on the unique path from \(X\) to \(Y\) and the number of those spies whose current danger value is greater than \(C\).

Note: A spy who has not started collecting intelligence has a danger value of \(0\). If a spy started collecting on day \(d\), then on day \(i\) (where \(i \ge d\)) his danger value is \(i - d\) (and remains \(0\) on day \(d\) itself).

outputFormat

For each task of the second type, output a line containing two space-separated integers: the total number of spies on the transmission path and the number of spies whose danger value exceeds \(C\) at the time of the task.

sample

5
1 1 2 2
6
1 3
2 4 5 0
1 2
2 4 5 0
2 3 4 1
2 1 5 0

3 0
3 1
4 2
3 1