Bình muốn xây dựng một từ điển điện tử. Ban đầu từ điển rỗng. Bình cần thực hiện \(N\) thao tác, mỗi thao tác thuộc một trong ba loại:

• 1 s: Thêm xâu \(s\) vào từ điển.
• 2 s: Hỏi xâu \(s\) có trong từ điển không.
• 3 s: Đếm số xâu trong từ điển có tiền tố là \(s\).

Hãy giúp Bình xây dựng từ điển.

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

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng là một thao tác. Tổng độ dài các xâu không quá \(10^5\).

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra YES hoặc NO (mỗi kết quả trên một dòng).
• Với mỗi thao tác loại 3, in ra số lượng xâu có tiền tố đó.

Ví dụ

Input:

7
1 apple
1 app
2 apple
2 banana
3 app
1 application
3 app

Output:

YES
NO
2
3

Ràng buộc

• 100% số điểm: Tổng độ dài các xâu \(\le 10^5\).