Hãy đọc các bài lật đổ google ~1 \ 2 \ 3~ để hiểu thêm về cốt truyện của bài này :>

Tới bước cuối cùng của quá trình chinh phục bá chủ thế giới, Pitomon đã bí idea cho công cụ tìm kiếm PitoSearch của mình và ý tưởng để viết đề bài này nên là ta hãy đi thẳng vào vấn đề.

Vẫn với dữ liệu cũ, là cái tên của ~n~ người xấu số bị rao bán thân phận của mình trên Deepweb, mỗi cái tên sẽ là ~1~ xâu kí tự gồm tối đa ~20~ kí tự và chỉ gồm các kí tự từ ~a \rightarrow z~.

Và để copy y nguyên công cụ tìm kiếm google, Pitomon muốn chôm cả tính năng gợi ý của google. Nhưng mà trình độ hạn chế nên thay vì hiển thị các từ khóa với độ phổ biến từ trên xuống dưới, công cụ PitoSearch sẽ hiển thị các từ gợi ý theo thứ tự bảng chữ cái alphabét :>

Và lần này, yêu cầu đề ra, sẽ có ~m~ truy vấn,truy vấn thứ ~i~ sẽ gồm ~1~ xâu kí tự ~S_i~ và ~1~ số nguyên ~K_i~, với yêu cầu là cần tìm và in ra tên có khả năng là ~S_i~ trong bộ dữ liệu và sắp xếp từ bé đến lớn thứ ~K_i~ trong danh sách các tên có khả năng là ~S_i~. Nếu không tìm thấy tên nào có khả năng là ~S_i~ hoặc có ít hơn ~K_i~ tên giống ~S_i~ trong bộ dữ liệu thì in ra ~-1~.

Ví dụ với truy vấn ~'pito'~ thì các tên có khả năng là ~'pitomon'~, ~'pitopotato'~, ~'pito'~ (Nghĩa là phần đầu của các tên phải trùng hoàn toàn với truy vấn, và độ dài của tên phải lớn hơn hoặc bằng truy vấn).

Input

• Dòng đầu tiên chứa 2 số nguyên ~n, m \ (1\le n, m\le 10^5)~ là số lượng dữ liệu đầu vào và số lần thử của Pitomon.
• ~n~ dòng tiếp theo, mỗi dòng gồm một chuỗi kí tự (độ dài không vượt quá ~20~ và chỉ gồm các kí tự từ ~a \rightarrow z~) mô tả từng tên người dùng trong bộ dữ liệu.
• ~m~ dòng tiếp theo, mỗi dòng gồm một chuỗi kí tự ~S_i~ (độ dài không vượt quá ~20~ và chỉ gồm các kí tự từ ~a \rightarrow z~) và một số nguyên ~K_i \ (1 \le K_i \le n)~.

Output

• Gồm ~m~ dòng, mỗi dòng là ~1~ xâu kí tự tìm được hoặc ~-1~ nếu không tìm được theo yêu cầu đề bài.

Scoring

• Subtask ~1~: có ~20\%~ số điểm với mọi ~K_i=1~ và mỗi truy vấn chỉ có nhiều nhất ~1~ tên có khả năng là tên đó trong dữ liệu.
• Subtask ~2~: có ~30\%~ số điểm với ~2 \leq n,m \leq 10^3~.
• Subtask ~3~: có ~50\%~ số điểm với ~10^3 < n,m\le 10^5~.

Sample Input 1

5 1
pitomon
pitopotato
pimon
pitodepchai
pitomenli
pito 3

Sample Output 1

pitomon

Sample Input 2

5 4
hieu
hieugay
donateforrank
mingming
donganhduong
dong 1
ming 2
hieu 1
hieu 2

Sample Output 2

donganhduong
-1
hieu
hieugay

Giải thích

- Với test mẫu thứ nhất, các tên có khả năng là "pito" là :
pitomon
pitopotato
pitodepchai
pitomenli
- Sau khi sắp xếp, các tên có thứ tự là :
pitodepchai
pitomenli
pitomon
pitopotato
Và lấy tên thứ 3 ta sẽ được "pitomon"