볼 머신

볼 머신은 루트가 있는 트리로, $N$개의 노드가 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 각 노드는 비어 있거나 공 하나를 담고 있습니다. 처음에는 모든 노드가 비어 있습니다. 이 기계는 두 종류의 연산을 지원합니다.

연산 1 — 공 $k$개 넣기. 공을 하나씩 루트에 떨어뜨립니다. 공은 현재 놓인 노드에 비어 있는 자식이 하나라도 있는 한 계속 아래로 굴러갑니다. 비어 있는 자식이 여러 개이면, 공은 그 서브트리에 가장 작은 노드 번호를 포함하는 자식으로 굴러갑니다. 비어 있는 자식이 없는 노드에 도달하면 공은 그 자리에 멈춥니다.

예를 들어 아래 그림의 기계에 공 두 개를 넣으면 공은 각각 1번과 3번 노드로 갑니다. 첫 번째 공은 4번에서 3번으로 굴러가는데, 3번이 비어 있고 그 서브트리(3번과 1번으로 구성됨)에 1번을 포함하기 때문입니다. 이어서 3번에서 1번으로 굴러갑니다. 두 번째 공도 4번에서 3번으로 굴러가 그곳에 멈춥니다.

연산 2 — 지정한 노드의 공 빼기. 지정한 노드가 비게 되고, 그 위쪽의 공들이 아래로 내려옵니다. 즉, 비어 있는 노드의 부모가 공을 가지고 있으면 그 공이 아래로 굴러 내려옵니다.

예를 들어 아래 그림의 기계에서 5번, 7번, 8번 노드의 공을 이 순서대로 빼면 1번, 2번, 3번 노드가 비게 됩니다.

첫 번째 줄에 두 정수 $N$과 $Q$가 주어집니다. 각각 노드의 개수와 연산의 개수입니다. 다음 $N$개의 줄 중 $i$번째 줄에는 정수 하나가 주어지는데, 노드 $i$의 부모 노드 번호이며, 노드 $i$가 루트이면 $0$입니다. 다음 $Q$개의 줄은 각각 하나의 연산을 나타냅니다. 1 k는 공 $k$개를 넣는 연산이고, 2 x는 노드 $x$의 공을 빼는 연산입니다.

주어지는 모든 연산은 항상 올바릅니다. 즉, 넣기 연산이 현재 비어 있는 노드 수보다 많은 공을 넣지 않으며, 빼기 연산이 비어 있는 노드를 대상으로 하지 않습니다.

각 연산에 대해 한 줄씩, 연산이 주어진 순서대로 정수 하나를 출력합니다.

• 유형 1 연산: 마지막으로 넣은 공이 최종적으로 멈춘 노드의 번호를 출력합니다.
• 유형 2 연산: 공을 뺀 뒤 아래로 굴러 내려온 공의 개수를 출력합니다.

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• 입력은 항상 정확히 하나의 루트(부모가 $0$)를 가진 하나의 트리를 나타냅니다.