Một nhóm kĩ sư phần mềm Z đang thử nghiệm ứng dụng gợi ý nhắn tin trên điện thoại với một bộ danh mục gồm \(n\) từ vựng, mỗi từ là một xâu chỉ gồm các kí tự latin in thường (từ a đến z). Khi người dùng nhập vào một từ \(W\) (cũng chỉ gồm các kí tự latin in thường), ứng dụng gợi ý sẽ liệt kê tất cả các từ vựng trong danh mục nhận \(W\) làm tiền tố để người dùng có thể nhanh chóng lựa chọn.

Một xâu \(A\) được gọi là tiền tố của xâu \(B\) nếu phần đầu của xâu \(B\) khớp với toàn bộ xâu \(A\), ví dụ: Xâu danang có các tiền tố là d, da, dan, dana, danan và danang.

Yêu cầu: Cho danh mục \(n\) từ vựng và \(m\) câu hỏi, câu hỏi thứ \(i\) có dạng \(k_i\) và từ \(W_i\). Hãy tìm từ vựng thứ \(k\) theo thứ tự từ điển mà ứng dụng sẽ gợi ý khi người dùng nhập vào từ \(W\) và in ra chỉ số của từ vựng đó trong danh mục (chỉ số danh mục được đánh từ \(1\) đến \(n\)).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(m\);
• Mỗi dòng trong \(n\) dòng tiếp theo chứa một từ vựng trong danh mục;
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa số nguyên dương \(k_i\) và từ \(W_i\) thể hiện một câu hỏi (\(|W_i| \le 1000\)).

Output

• Ghi ra \(m\) dòng, dòng thứ \(i\) chứa một số nguyên là câu trả lời cho câu hỏi thứ \(i\), hoặc số nguyên \(-1\) nếu không tồn tại một xâu như vậy.

Example

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

3
1
-1

Ràng buộc

• Có \(50\%\) số test ứng với \(50\%\) số điểm thoả mãn: \(n \le 3000, m \le 300\) và các từ có độ dài không quá \(50\);
• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm thoả mãn: \(n \le 3000, m \le 10000\) và tổng độ dài các từ không vượt quá \(10^6\).