Một “máy thả bóng” có dạng cây có gốc, gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Mỗi đỉnh hoặc rỗng, hoặc chứa đúng một quả bóng. Ban đầu mọi đỉnh đều rỗng. Máy thực hiện hai loại thao tác:

1. Thêm \(k\) quả bóng: Lần lượt đặt từng quả bóng vào đỉnh gốc. Chừng nào đỉnh đang chứa quả bóng còn có một đỉnh con rỗng, quả bóng sẽ lăn xuống. Nếu có nhiều đỉnh con rỗng, quả bóng chọn đỉnh con có cây con chứa đỉnh mang số nhỏ nhất. Quy tắc này được áp dụng lại ở mỗi tầng mà quả bóng đi qua. Chẳng hạn, khi thêm hai quả bóng vào máy dưới đây, chúng dừng ở các đỉnh \(1\) và \(3\). Quả thứ nhất đi từ \(4\) xuống \(3\) vì cây con của \(3\) chứa đỉnh \(1\), rồi tiếp tục xuống \(1\). Quả thứ hai cũng đi từ \(4\) xuống \(3\) và dừng lại.

   

2. Lấy một quả bóng khỏi đỉnh được chỉ định: Đỉnh đó trở thành rỗng và các quả bóng ở phía trên, nếu có, lăn xuống. Khi cha của một đỉnh rỗng có bóng, quả bóng ở đỉnh cha sẽ lăn xuống đỉnh rỗng đó. Nếu lần lượt lấy bóng khỏi các đỉnh \(5\), \(7\), \(8\) trong máy dưới đây, các đỉnh \(1\), \(2\), \(3\) sẽ trở thành rỗng.

   

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(Q\), lần lượt là số đỉnh và số thao tác.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số hiệu cha của đỉnh \(i\), hoặc \(0\) nếu \(i\) là gốc.

Mỗi dòng trong \(Q\) dòng tiếp theo mô tả một thao tác:

• 1 k: thêm \(k\) quả bóng vào máy.
• 2 x: lấy một quả bóng khỏi đỉnh \(x\).

Mọi thao tác đều hợp lệ: số bóng được thêm không vượt quá số đỉnh rỗng, và thao tác lấy bóng luôn chỉ đến một đỉnh đang có bóng.

Dữ liệu ra

Với mỗi thao tác loại \(1\), in số hiệu đỉnh mà quả bóng được thêm cuối cùng dừng lại. Với mỗi thao tác loại \(2\), in số quả bóng đã lăn xuống sau khi lấy quả bóng được chỉ định. Mỗi kết quả nằm trên một dòng riêng.

Ràng buộc

• \(1 \le N,Q \le 100\,000\).
• \(1 \le k \le N\) và \(1 \le x \le N\), đồng thời các thao tác thỏa điều kiện hợp lệ nêu trên.

Phân nhóm

• Nhóm \(25\) điểm: mỗi đỉnh có đúng \(0\) hoặc \(2\) đỉnh con; mọi đỉnh không có con đều cách gốc một khoảng bằng nhau.
• Nhóm \(30\) điểm: các thao tác được chọn sao cho không có quả bóng nào lăn xuống sau bất kỳ thao tác loại \(2\) nào.
• Nhóm \(40\) điểm: có đúng một thao tác loại \(1\), và đó là thao tác đầu tiên.
• \(5\) điểm còn lại: không có ràng buộc bổ sung.

Ba tập dữ liệu tương ứng với các nhóm \(25\), \(30\) và \(40\) điểm đôi một không giao nhau.

Ví dụ

8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8

1
3
2
2