Hệ thống tra cứu từ điển của thư viện Đại học FPT cần quản lý một tập từ vựng tiếng Anh. Bạn được yêu cầu lập trình mô phỏng một cấu trúc dữ liệu cây tiền tố (Trie) để thực hiện ba loại thao tác:

• 1 S: Thêm xâu ký tự \(S\) vào tập từ vựng.
• 2 S: Kiểm tra xem xâu \(S\) có tồn tại trong tập từ vựng không. In ra YES hoặc NO.
• 3 P: Kiểm tra xem có từ nào trong tập từ vựng bắt đầu bằng tiền tố \(P\) không. In ra YES hoặc NO.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^5\)) — số lượng thao tác.
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác có cấu trúc như mô tả.

Định dạng đầu ra

• Với mỗi thao tác loại 2 và 3, in ra kết quả YES hoặc NO tương ứng trên một dòng riêng biệt.

Ví dụ

Input:

6
1 apple
2 apple
2 app
3 app
1 app
2 app

Output:

YES
NO
YES
YES

Ràng buộc

• 30% số điểm ứng với \(Q \le 1000\) và tổng độ dài các xâu \(\le 5000\).
• 70% số điểm còn lại có tổng độ dài các xâu không vượt quá \(10^6\). Các ký tự trong xâu chỉ gồm chữ cái tiếng Anh in thường a-z.