Cho dãy số nguyên \((a)\) được bắt đầu từ chỉ số \(1\). Với mỗi truy vấn dạng \(x\:l\:r\) \((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*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\%\) số test có \(n, q \le 200\).

\(30\%\) 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