Cho dãy số nguyên $(a)$ được bắt đầu từ chỉ số $1$. Với mỗi truy vấn dạng $xlr$ $(l\le r)$ hãy tìm phần tử gần $x$ nhất trong các số $a_l,a_{l+1},...,a_r$ và số lượng phần tử như vậy.

Đầu vào

Dòng đầu gồm hai số tự nhiên $n$ và $q$ $(1\le n,q\le 2\ast {10}^5)$ lần lượt là số phần tử dãy $(a)$ và số lượng truy vấn.

Dòng tiếp theo chứa $n$ số nguyên trong khoảng $[-33000,33000]$ là các phần tử của dãy $(a)$.

$q$ dòng tiếp theo mỗi dòng chứa một ba số nguyên $x,l,r$ $(1\le l\le r\le n)$ là một truy vấn.

Đầu ra

$q$ dòng, mỗi dòng gồm hai số tự nhiên là trả lời của một truy vấn: số đầu tiên là phần tử gần nhất trong dãy con, số tiếp theo là số lượng phần tử như vậy.

Ghi chú: Nếu có hai phần tử giá trị khác nhau trên một khoảng cùng gần nhất với $x$ thì chọn phần tử có giá trị nhỏ hơn và chỉ đếm phần tử này.

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Subtask

$30\mathrm{\%}$ số test có $n,q\le 200$.

$30\mathrm{\%}$ số test có $n,q\le 2000$.

Ví dụ

Đầu vào:

6 2
-1 1 4 3 5 1
1 1 6
5 2 4

Đầu ra:

1 2
4 1