EIU Programming Practices and Exams

Trường Đại học Quốc Tế Miền Đông chuẩn bị tổ chức kì thi lập trình quốc tế ACM/ICPC, có N sinh viên trong nước đến tham gia, số báo danh của các sinh viên được đánh số từ 1 đến N theo danh sách tên đã sắp xếp với độ ưu tiên: Tên, Họ, Tên Đệm

Do biết có nhiều sinh viên sẽ chỉ nhớ tên mà quên số báo danh, nhà trường muốn phát triển một phần mềm nhập tên sinh viên và trả về số báo danh của sinh viên đó. Do đội ngũ lập trình viên không đủ, nhà trường cần sự giúp đỡ từ các sinh viên trong trường.

Input

Dòng thứ nhất gồm hai số nguyên N và M (1 ≤ N, M ≤ 10^5) - lần lượt là số lượng sinh viên trong danh sách và số lượng sinh viên cần tìm kiếm.

N dòng tiếp theo, mỗi dòng gồm tên sinh viên ([Họ] [Tên đệm] Tên) - bao gồm khoảng trắng và các kí tự thường từ a-z. Đảm bảo tên đầy đủ của các sinh viên không trùng nhau. Dữ liệu nhập vào bắt buộc phải có phần tên, nhưng không nhất thiết có phần họ và tên đệm.

M dòng tiếp theo, mỗi dòng gồm tên sinh viên cần tìm.

Chú ý: xem testcase mẫu để hiểu rõ input.

Output

Xuất ra mã số báo danh của mỗi sinh viên cần tìm, sinh viên không tồn tại xuất ra -1.

Câu hỏi bổ sung: Trong trường hợp tổng quát giải thuật sort nào thường được sử dụng, độ phức tạp của giải thuật như thế nào. Có thư viện nào hỗ trợ giải thuật này không?

Example

Input:
3 2
tran cong duy
luu nhat phi
nguyen manh phuc
nguyen manh phuc
tran duy

Output:
3
-1