Tìm kiếm động cơ

View as PDF

Submit solution


Points: 0.01 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

[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.

image

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 POSTDELETE đả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

Comments

Please read the guidelines before commenting.



  • -8
    Myee  commented on April 25, 2023, 5:18 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.