Gợi ý từ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một từ điển gồm $W$ từ và $N$ truy vấn. Mỗi truy vấn gồm một số nguyên $K$ và một xâu tiền tố $p$ . Hãy tìm từ thứ $K$ (theo thứ tự từ điển) trong số các từ của từ điển bắt đầu bằng $p$ . In ra vị trí gốc (chỉ số 1-based trong danh sách từ điển ban đầu) của từ đó, hoặc $- 1$ nếu không tồn tại đủ $K$ từ khớp.

Dữ liệu vào

Dòng 1: Hai số nguyên $W$ ( $1 \leq W \leq 1000$ ) và $N$ ( $1 \leq N \leq 1000$ ).
$W$ dòng tiếp theo: Mỗi dòng là một từ trong từ điển (chỉ gồm chữ cái thường a-z).
$N$ dòng tiếp theo: Mỗi dòng gồm số nguyên $K_{i}$ và xâu tiền tố $p_{i}$ .

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên: chỉ số gốc (1-based) của từ thứ $K$ theo thứ tự từ điển bắt đầu bằng $p$ , hoặc $- 1$ nếu không đủ.

Ràng buộc

$1 \leq W, N \leq 1000$
Tổng độ dài các từ trong từ điển $\leq 10^{6}$
Độ dài mỗi tiền tố truy vấn $\leq 1000$

Ví dụ

Input	Output	Giải thích
10 3 dab ba ab daa aa aaa aab abc ac dadba 4 a 2 da 4 da	3 1 -1	Truy vấn 1: Các từ bắt đầu bằng "a" theo thứ tự từ điển: aa, aaa, aab, ab, abc, ac → từ thứ 4 là "ab" (vị trí gốc 3). Truy vấn 2: Các từ bắt đầu bằng "da" theo thứ tự từ điển: daa, dab, dadba → từ thứ 2 là "dab" (vị trí gốc 1). Truy vấn 3: Chỉ có 3 từ bắt đầu "da", không đủ 4.

Bình luận

Không có bình luận tại thời điểm này.