题目描述

小晓特别“二”，所以她对“二”特别喜欢。她现在拿到 $n$ 了个数 $s[1] \sim s[n]$，然后她想知道对于第 $a$ 到第 $b$ 个数，其中第二大或者第二小的数是多少呢？

输入格式

第一行，两个正整数 $n$ 和 $k$ 。

第二行 $n$ 个正整数，为小晓拿到的 $n$ 个数 $s[1] \sim s[n]$。

接下来 $k$ 行，每行两个正整数 $a$ 和 $b$，为询问的区间。

数据范围

50% 的数据，$1 \le n,k \le 100$

100% 的数据，$1 \le a \lt b \le n \le 100000$, $1 \le k \le 1000$, $1 \le s[i] \le 10^9$

输出格式

共 k 行，每行两个正整数，分别为第二大数和第二小数，中间用空格隔开。

样例

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

3 2
4 3