Gợi ý từ

Cho một từ điển gồm $W$ từ. Với mỗi truy vấn, bạn cần tìm từ thứ $K$ theo thứ tự bảng chữ cái trong số các từ trong từ điển có tiền tố là xâu cho trước. Nếu không tồn tại từ thứ $K$ như vậy, trả về $-1$.

Dữ liệu vào

• Dòng 1: Hai số nguyên $W$ và $N$ — số từ trong từ điển và số truy vấn.
• $W$ dòng tiếp theo: Mỗi dòng là một từ trong từ điển (chỉ gồm chữ thường a–z). Các từ được đánh số từ $1$ đến $W$ theo thứ tự xuất hiện.
• $N$ dòng tiếp theo: Mỗi dòng là một truy vấn gồm số nguyên $K_i$ và một xâu $p_i$ — tìm từ thứ $K_i$ theo thứ tự từ điển trong số các từ có tiền tố là $p_i$.

Dữ liệu ra

Với mỗi truy vấn, in ra chỉ số (1-based) trong từ điển của từ cần tìm. Nếu không tồn tại, in ra $-1$.

Ràng buộc

• $1\le W$; tổng độ dài tất cả các từ trong từ điển $\le {10}^6$
• $1\le N\le 10000$; độ dài mỗi xâu truy vấn $\le 1000$
• $1\le K_i\le {10}^6$

Ví dụ