Mỗi cuốn sách trong thư viện đều có một mã sách dùng để tra cứu nhanh, mã sách là một số nguyên dương. Mỗi bạn đọc đến mượn sách cầm trong tay một mã yêu cầu, mã yêu cầu cũng là một số nguyên dương. Nếu mã sách của một cuốn sách có phần kết thúc đúng bằng mã yêu cầu của bạn đọc thì cuốn sách đó chính là cuốn mà bạn đọc này cần. Bình vừa trở thành thủ thư của thư viện, cô biết mã sách của tất cả các cuốn sách trong thư viện. Cô nhờ bạn viết một chương trình: với mỗi bạn đọc, tìm cuốn sách có mã sách nhỏ nhất trong số những cuốn sách mà bạn đọc đó cần; nếu không có cuốn nào mà bạn đọc đó cần, hãy in ra -1.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên dương $n,q$, cách nhau một dấu cách, lần lượt là số cuốn sách trong thư viện và số bạn đọc.

$n$ dòng tiếp theo, mỗi dòng gồm một số nguyên dương, là mã sách của một cuốn sách trong thư viện.

$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương cách nhau một dấu cách: số nguyên dương thứ nhất là độ dài mã yêu cầu của bạn đọc, số nguyên dương thứ hai là mã yêu cầu của bạn đọc.

Dữ liệu ra

$q$ dòng, mỗi dòng gồm một số nguyên: nếu tồn tại cuốn sách mà bạn đọc thứ $i$ cần thì ở dòng thứ $i$ in ra mã sách nhỏ nhất trong số các cuốn sách mà bạn đọc thứ $i$ cần, ngược lại in ra $-1$.

Ví dụ

Input

5 5 
2123 
1123 
23 
24 
24 
2 23 
3 123 
3 124 
2 12 
2 12

Output

23 
1123 
-1 
-1 
-1

Ghi chú

Phạm vi dữ liệu

Với $20\%$ số dữ liệu, $1 \le n \le 2$.

Có thêm $20\%$ số dữ liệu thỏa mãn $q = 1$.

Có thêm $20\%$ số dữ liệu trong đó mã yêu cầu của mọi bạn đọc đều có độ dài $1$.

Có thêm $20\%$ số dữ liệu trong đó các mã sách được cho theo thứ tự tăng dần.

Với $100\%$ số dữ liệu, $1 \le n \le 1000,1 \le q \le 1000$, mọi mã sách và mã yêu cầu đều không vượt quá $10^7$.

Nguồn: NOIP2017 bảng phổ cập T2