Trung vị của dãy số

Cho dãy số gồm \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\). Trung vị của một dãy số có \(N\) là phần tử ở vị trí \(\left\lfloor \frac{N+1}{2} \right\rfloor\) của dãy số đó sau khi đã sắp xếp.

Bạn cần trả lời \(Q\) lệnh hỏi trên dãy số ban đầu, mỗi lệnh hỏi cho bởi cặp số \([L, R]\) và yêu cầu tìm trung vị của dãy con liên tiếp được giới hạn bởi chỉ số đầu là \(L\) và chỉ số cuối là \(R\).

Ví dụ: dãy \(a\) gồm các số \(15, 6, 8, 11, 7\). Kết quả lệnh hỏi \([1, 2]\) là \(6\); kết quả lệnh hỏi \([2, 5]\) là \(7\); kết quả lệnh hỏi \([1, 5]\) là \(8\).

Input

Dữ liệu vào từ bàn phím gồm:

• Dòng 1: chứa số nguyên dương \(N\) và \(Q\) (\(N, Q \le 10^5\)).

• Dòng 2: chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (với \(a_i \le 10^9\), \(1 \le i \le N\)).

• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)).

Ràng buộc:

• Có \(30\%\) số test có \(N, Q \le 500\).

• Có \(30\%\) số test khác có \(N, Q \le 10^4\).

• Có \(40\%\) số test còn lại không có giới hạn gì thêm.

Output

Ghi ra màn hình gồm \(Q\) dòng, mỗi dòng là kết quả của một lệnh hỏi tương ứng với dữ liệu vào.

Example

Input:

5 3
25 36 8 11 17
1 2
2 5
1 5

Output:

25
11
17

Note

Kết quả lệnh hỏi \([1, 2]\) là \(25\). Kết quả lệnh hỏi \([2, 5]\) là \(11\). Kết quả lệnh hỏi \([1, 5]\) là \(17\).