Tìm kiếm động cơ
Xem dạng PDF[placeholder] đang muốn trở thành 1 tỉ phú.
Đến thời điểm hiện tại, [placeholder] đã hoàn thành được giai đoạn 1 của công cuộc trở thành tỉ phú: bỏ học.
Không bỏ phí một giây nào, [placeholder] lập tức quyết định bắt đầu giai đoạn 2: tạo ra tìm kiếm động cơ G****e. Mỗi giây, tìm kiếm động cơ G****e của [placeholder] phải xử lý được các truy vấn sau:
- POST x c: Thêm 1 xâu được tạo bằng cách lấy xâu tại giây thứ ~x~ và
nối vào đó chữ cái ~c~
- DELETE x: Xâu được tạo ra vào giây thứ ~x~ được xóa bỏ. Nếu xâu tại
thời điểm ~x~ đã bị xóa từ trước thì G****e không làm gì cả.
- GET s k: Cho xâu ~s~, tìm xâu có thứ tự từ điển thứ ~k~ nhận ~s~
làm tiền tố
Đang chuẩn bị code thì [placeholder] bỗng nhớ ra 1 bài học từ môn Tư duy Sigma nam tại Đại học Chen lấn của hàng đầu G nổi tiếng Ăn riêu Tết: một Sigma nam không bao giờ tự làm công việc tay chân. Vì vậy, [placeholder] đã quyết định thuê bạn code, rồi dùng thời gian quý báu của bản thân để retweet nhà thầu khoán đại tài Melon Husk.
Input
Dòng đầu tiên chứa số ~n~ (~n \le 250000~), số giây tìm kiếm động cơ G****e phải chạy. ~n~ dòng tiếp theo, mỗi dòng là một truy vấn.
Các truy vấn POST và DELETE đảm bảo tại giây thứ ~x~ cũng là một
truy vấn POST. Quy ước xâu tạo ra vào giây ~0~ là xâu rỗng. Input đảm
bảo trong mọi thời điểm các xâu chưa bị xóa đều phân biệt.
Tổng độ dài các xâu ~s~ không vượt quá ~10^6~.
Output
Với mỗi truy vấn GET, in ra trên ~1~ dòng thời điểm đáp án xâu đó được
tạo ra. Trong trường hợp không tồn tại ít nhất ~k~ xâu hợp lệ, in ra
"404".
Sample Input 1
13
POST 0 l
POST 1 m
POST 2 a
POST 3 o
POST 1 o
POST 5 l
POST 3 i
POST 3 u
GET lmao 1
GET lmao 2
GET lma 2
DELETE 7
GET lma 2
Sample Output 1
4
404
7
4
Bình luận
Đề viết rất hay
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.