[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
đề gốc bài này vnoi hay codeforces vậy mn
Đề 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.