Duy trì một kho từ ban đầu rỗng, hỗ trợ thêm từ, kiểm tra một từ đã được thêm và kiểm tra có từ nào mang một tiền tố cho trước.
Lệnh chỉ đúng khi toàn bộ đã được thêm trước đó. Lệnh đúng khi tồn tại ít nhất một từ đã thêm bắt đầu bằng ; bản thân không nhất thiết là một từ hoàn chỉnh.
Input
- Dòng đầu chứa số thao tác .
- Mỗi trong dòng tiếp theo chứa một lệnh insert, search hoặc prefix và một chuỗi .
Output
- Với mỗi lệnh search hoặc prefix, in YES nếu điều kiện tương ứng đúng, ngược lại in NO.
Constraints
- .
- .
- Mọi ký tự của thuộc .
- Tổng độ dài các chuỗi trong toàn bộ thao tác không vượt quá .
Scoring
- Subtask ( số điểm): và tổng độ dài các chuỗi không vượt quá .
- Subtask ( số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
10 insert can search can search ca prefix ca insert cap prefix cat insert ca search ca prefix c search cap
Output
YES NO YES NO YES YES YES
Giải thích: Sau khi thêm can, chuỗi ca mới chỉ là tiền tố nên search ca trả NO, còn prefix ca trả YES. Việc thêm ca về sau đánh dấu chính nút đó là một từ hoàn chỉnh; cap cũng được tìm thấy ở truy vấn cuối.