Ball Rolling on a Tree

We are given a tree with n nodes numbered from 1 to n with node 1 as the root. Each node can hold at most one ball. Initially, all nodes are empty. The tree structure is given by specifying the parent for every node i (2 ≤ i ≤ n).

A ball will roll down the tree following the rules below:

• Insertion: When balls are inserted (operation type 1 k), you try to put k balls at the root one by one. For each ball, if the current node is empty, put the ball there and then simulate gravity: while the current node u has at least one child that is empty, the ball rolls to the empty child v that is chosen according to the following criterion: if a node u has children, sort them in increasing order by the minimum node number in their respective subtrees (including the child itself). The ball always rolls to the first child (i.e. the one with the smallest such value) that is empty. If the current node is already occupied, then the ball is not inserted (each position can hold only one ball).
• Removal: In a removal operation (operation type 2 v), the ball at node v is removed. After a ball is removed, gravity works upward: if the parent of the now-empty node is holding a ball and has an empty child slot (determined by the same ordering rule), then that ball will roll down to fill the first available empty child. This process repeats upward until no more moves can be made.

Formally, let the ordered list of children for a node u be sorted by the minimum node number in the corresponding subtree. When a ball is at node u and there is at least one child v with v empty (considering the order), the ball moves from u to that child and u becomes empty. Similarly, when a ball is removed from a node, the process checks the parent: if the parent is holding a ball and its first empty child exists, then that ball rolls into that slot, leaving the parent empty, and the cascade continues upward.

You are given a sequence of operations. After processing all operations, output the final occupancy of nodes in the tree (output 1 if the node contains a ball, or 0 otherwise).

Input in brief:

• First line contains two integers n and m — the number of nodes and the number of operations.
• Second line contains n-1 integers: for i = 2 to n, the i-th integer is the parent of node i.
• Next m lines, each describes an operation. An operation of the form 1 k means insert k balls (one at a time) at the root. An operation of the form 2 v means remove the ball from node v (it is guaranteed that the removal operation is valid).

Output in brief:

• Print one line containing n space‐separated integers. The i-th integer should be 1 if node i has a ball in the final configuration, or 0 otherwise.

inputFormat

The input consists of:

• The first line contains two integers n (number of nodes) and m (number of operations).
• The second line contains n-1 integers: for each node i (2 ≤ i ≤ n), an integer representing the parent of node i.
• The next m lines each contain an operation in one of the following formats:
• 1 k — insert k balls at the root (one by one).
• 2 v — remove the ball from node v.

outputFormat

Output one line with n space-separated integers. The i-th integer is 1 if node i contains a ball in the final configuration, or 0 otherwise.

sample

5 5
1 1 2 2
1 1
1 1
2 4
1 2
2 2

0 0 0 1 1