Người ta gieo một (vài) hạt xuống đất. Sau vài năm, những hạt đó trưởng thành, trở thành cây và mọc nhánh. Mỗi đoạn nhánh đều có trọng lượng khác nhau. Đôi khi, bão tới, mưa to gió lớn và công ty cây xanh phải cắt bỏ đi một phần nhánh cây.

Chúng ta sẽ mô phỏng điều này. Ban đầu, chúng ta có một cây có ~n = 1~ đỉnh, đỉnh gốc đó được đánh số ~0~. Chúng ta cũng có ~q~ truy vấn, mỗi truy vấn sẽ thực hiện một trong những hành động sau:

• 1: "+ u" ~(0 \le u < n)~: Tạo đỉnh mới có nhãn đánh số ~i = n~, sau đó ~n~ tăng thêm ~1~ đơn vị. Nối đỉnh ~i~ vào đỉnh ~u~ và lúc này ~u~ sẽ là cha (tổ tiên trực tiếp) của ~i~.

• 2: "- u" ~(0 \le u < n)~: Xóa bỏ cây con gốc ~u~.

• 3: "? u" ~(0 \le u < n)~: Đếm và cho biết số lượng đỉnh trong cây con gốc ~u~, bao gồm chính đỉnh ~u~.

Với mỗi truy vấn loại ~3~, bạn hãy in ra kết quả của câu hỏi đó.

Input

• Dòng đầu tiên gồm số ~q~ ~(1 \le q \le 10^5)~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ lần lượt chứa ký tự ~c~ và số ~u~, cho biết nội dung của truy vấn. Đề bài đảm bảo các điều kiện sau tại ngay trước thời điểm hỏi của mỗi truy vấn: ~c~ là một trong các ký tự +, -, ?; ~0 \le u < n~ và ~u~ chưa bị xóa.

Output

• Với lần lượt mỗi truy vấn loại ~3~, in ra một dòng một số duy nhất là kết quả truy vấn.

Scoring

Sample Input 1

7
+ 0
+ 0
- 1
? 0
+ 2
- 3
? 2

Sample Output 1

2
1