Chức năng tự động gợi ý từ khóa (Autocomplete) của công cụ tìm kiếm FPTOJ quản lý một danh sách gồm \(N\) từ khóa. Mỗi từ khóa \(S_i\) có một độ phổ biến (tần suất tìm kiếm) tương ứng là \(W_i\).

Khi người dùng nhập một tiền tố \(P\), hệ thống cần gợi ý từ khóa có độ phổ biến lớn nhất bắt đầu bằng tiền tố \(P\). Nếu có nhiều từ khóa cùng độ phổ biến lớn nhất, hãy chọn từ khóa có thứ tự từ điển nhỏ hơn. Nếu không có từ khóa nào phù hợp, in ra -1.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 5 \cdot 10^4\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một từ khóa \(S_i\) và số nguyên dương \(W_i\) (\(1 \le W_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một tiền tố truy vấn \(P\).

Định dạng đầu ra

• Với mỗi truy vấn tiền tố, in ra từ khóa gợi ý tốt nhất, hoặc -1 nếu không có từ nào thỏa mãn.

Ví dụ

Input:

4 3
apple 10
apply 15
apricot 8
banana 20
app
ap
xyz

Output:

apply
apply
-1

Ràng buộc

• 30% số điểm ứng với \(N, Q \le 1000\) và tổng độ dài xâu \(\le 5000\).
• 70% số điểm còn lại có tổng độ dài các xâu không vượt quá \(5 \cdot 10^5\). Các ký tự chỉ gồm chữ cái tiếng Anh in thường.