Bessie có một chiếc điện thoại di động mới và rất thích gửi tin nhắn, mặc dù cô thường xuyên mắc lỗi chính tả vì bộ móng lớn khiến cô khó gõ trên màn hình nhỏ. Farmer John đồng ý giúp cô bằng cách viết một ứng dụng tự động hoàn thành từ: ứng dụng nhận một phần đầu của từ và đề xuất cách hoàn thành nó.

Ứng dụng tự động hoàn thành có quyền truy cập vào một từ điển gồm \(W\) từ, mỗi từ chỉ gồm các chữ cái thường từ a đến z, và tổng số chữ cái của tất cả các từ không vượt quá \(1\,000\,000\). Đầu vào của ứng dụng còn có danh sách \(N\) phần đầu của từ (\(1 \le N \le 1\,000\)), mỗi phần gồm không quá \(1\,000\) chữ cái thường. Cùng với mỗi phần đầu thứ \(i\), một số nguyên \(K_i\) cũng được cung cấp; ứng dụng phải tìm từ thứ \(K_i\) theo thứ tự bảng chữ cái trong số các từ nhận phần đầu thứ \(i\) làm tiền tố. Nói cách khác, nếu sắp xếp tất cả các cách hoàn thành hợp lệ của phần đầu thứ \(i\), ứng dụng phải đưa ra cách hoàn thành đứng thứ \(K_i\) trong dãy này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(W\) và \(N\).
• \(W\) dòng tiếp theo, dòng thứ \(i\) trong số này chứa từ thứ \(i\) của từ điển.
• \(N\) dòng cuối, dòng thứ \(i\) trong số này chứa một số nguyên \(K_i\), theo sau là một phần đầu của từ.

Ràng buộc

• \(1 \le N \le 1\,000\).
• Tổng số chữ cái trong tất cả các từ của từ điển không vượt quá \(1\,000\,000\).
• Mỗi phần đầu của từ chứa không quá \(1\,000\) chữ cái thường.
• Tất cả các từ và phần đầu của từ chỉ chứa các chữ cái thường từ a đến z.

Dữ liệu ra

Với mỗi phần đầu thứ \(i\), in ra trên một dòng chỉ số trong từ điển (một số nguyên từ \(1\) đến \(W\)) của cách hoàn thành thứ \(K_i\) theo thứ tự bảng chữ cái, hoặc \(-1\) nếu có ít hơn \(K_i\) cách hoàn thành.

Ví dụ

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

3
1
-1

Nguồn

USACO 2014 February Contest, Silver — Auto-Complete

Tác giả: Traditional.