Cho mảng ~a~ gồm ~n~ phần tử được sắp xếp không giảm và ~q~ truy vấn. Mỗi truy vấn chứa số ~x~; hãy tìm vị trí xuất hiện đầu tiên và cuối cùng của ~x~ trong mảng.

Dữ liệu vào

Dòng đầu chứa ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ theo thứ tự không giảm.

Dòng thứ ba chứa ~q~.

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~.

Dữ liệu ra

Với mỗi truy vấn, in hai số là vị trí đầu tiên và cuối cùng của ~x~. Nếu ~x~ không xuất hiện, in ~-1~ ~-1~.

Giới hạn

~1 \le n, q \le 100000~, ~1 \le a_i, x \le 10^{9}~.

V? d?

Input

1
1
3
1
2
0

Output

1 1
-1 -1
-1 -1