Cho một rừng cây gồm các cây có gốc, ban đầu chỉ có một cây gồm duy nhất một đỉnh được đánh số \(1\). Trong cùng một thành phần liên thông (giả sử chung một cây có gốc là \(r\)), ta có các định nghĩa sau:

• Đỉnh \(p\) được gọi là tổ tiên trực tiếp của đỉnh \(u\) nếu \(p\) kề với \(u\) và đường đi qua ít cạnh nhất giữa \(r\) và \(p\) không chứa \(u\).
• Đỉnh \(p\) được gọi là tổ tiên của \(u\) nếu đường đi qua ít cạnh nhất giữa \(r\) và \(u\) có chứa \(p\).
• Cây con gốc \(p\) bao gồm \(p\) và tất cả các đỉnh nhận \(p\) là tổ tiên của chúng.

Bạn cần giải quyết \(q\) truy vấn thuộc một trong ba loại sau:

• A u: Nếu rừng đang có \(n\) đỉnh, tạo một đỉnh mới đánh số \(n + 1\) có tổ tiên trực tiếp là đỉnh \(u\) (\(1 \leq u \leq n\)).
• C u: Cắt đi cạnh nối giữa đỉnh \(u\) và tổ tiên trực tiếp của nó để tạo thành một cây con mới có gốc là \(u\). Dữ liệu đảm bảo \(u > 1\) và đỉnh \(u\) chưa từng bị cắt trước đó.
• ? u: Đếm số lượng đỉnh của cây con gốc \(u\) (\(1 \leq u \leq n\), với \(n\) là số lượng đỉnh hiện tại của rừng).

Input

• Dòng đầu tiên chứa số \(q\) (\(1 \leq q \leq 5 \cdot 10^5\))
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn lần lượt chứa một ký tự \(c\) (\(c \in\) {A, C, ?}) và số nguyên dương \(u\). Dữ liệu đầu vào được đảm bảo hợp lệ với đề bài.

Output

• Với mỗi truy vấn ? u, in ra một dòng là kết quả cần tìm.

Example

10
? 1
A 1
A 1
A 2
A 4
A 2
? 4
C 2
? 1
? 4

1
2
2
2

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(q \leq 10\,000\)
• Subtask \(2\) (\(15\%\) số điểm): Không có truy vấn ? u nào nằm trước các truy vấn loại khác
• Subtask \(3\) (\(20\%\) số điểm): Không tồn tại truy vấn C u
• Subtask \(4\) (\(25\%\) số điểm): Với mọi truy vấn A u, nếu rừng đang có \(n\) đỉnh, dữ liệu đảm bảo \(u = n\)
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc nào thêm