Cho một hoán vị ~p~ của các số nguyên từ ~1~ đến ~n~. Gọi ~(l,r)~ là một dãy con liên tiếp của ~p~ từ vị trí ~l~ đến ~r~: ~p_l,p_{l+1},...,p_r~.

Sắp xếp toàn bộ các dãy con liên tiếp của ~p~ theo thứ tự từ điển tăng dần. Do có tới ~\dfrac{n\times(n + 1)}2~ dãy con liên tiếp, bạn chỉ cần trả lời ~q~ truy vấn: Hãy tìm dãy con liên tiếp có thứ tự từ điển thứ ~k~.

Cho hai dãy số nguyên khác nhau ~\alpha_1, \alpha_2, \dots, \alpha_\mu~, và ~\beta_1, \beta_2, \dots, \beta_\nu~. Dãy ~\alpha~ có thứ tự từ điển nhỏ hơn dãy ~\beta~ nếu:

• Tồn tại một chỉ số ~\iota~ sao cho ~\alpha_\nu = \beta_\nu~ ~\forall \nu < \iota~ và ~\alpha_\iota < \beta_\iota~.
• Nếu không tồn tại chỉ số ~\iota~ thỏa mãn, ~\nu < \mu~.

Ví dụ ~(1, 3, 2, 4)~ có thứ tự từ điển nhỏ hơn ~(1, 4, 2)~ vì vị trí thứ hai có ~3 < 4~. ~(1, 2, 3)~ có thứ tự từ điển nhỏ hơn ~(1,2,3,4)~.

Dữ liệu vào

• Dòng đầu tiên là số nguyên $n,q$ ~(1 \le n,q \le 2 \times 10^5)~.
• Dòng thứ hai gồm $n$ số nguyên $p_i$, một hoán vị của các số nguyên từ $1$ đến $n$.
• $q$ dòng tiếp theo, mỗi dòng là một số nguyên $k$, một truy vấn ~(1 \le k \le \dfrac{n\times (n + 1)}2)~.

Dữ liệu ra

• Với mỗi truy vấn, in ra hai số nguyên $l,r$, thể hiện dãy con liên tiếp từ $l$ đến $r$ là đáp án.

Ví dụ

Đầu vào

3 6
3 1 2
1
2
3
4
5
6

Đầu ra

2 2
2 3
3 3
1 1
1 2
1 3

Subtask

• Subtask 1 ($20\%$ số điểm): $1 \le n,q \le 200$.
• Subtask 2 ($20\%$ số điểm): $1 \le n \le 2000$.
• Subtask 3 ($20\%$ số điểm): $1 \le q \le 10$.
• Subtask 4 ($20\%$ số điểm): $p_i = i$.
• Subtask 5 ($20\%$ số điểm): Không có giới hạn gì thêm.