题目描述

又是一年 CSP，各位 TYOIER 们即将出征，为了让神犇们可以填满肚子以便应战，chxlong 让 lily 去买一些泡面（难道大佬们只有泡面？），lily 去 拼夕夕 挑了 $n$ 种泡面，$(n≤10^6)$。chxlong 和 lily 都想选出最好的泡面，但是他们又有些选择困难症，因此，他们选出了 $t$ 个区间，$(t≤10^3)$ 对于一个区间 $[l,r],\ (1≤l,r≤10^9)$ ，勤俭持家的 chxlong 希望挑选出最便宜的一种泡面，而一心一意想让同学们吃好睡好的 lily 希望找出最贵的，毕竟一分钱一分货。于是，他们找来了计算机高手 jy123，希望他能帮他们找到他们想要的泡面，并且获得他们的价格。但是，聪（jiao）明（hua） 的 jy123 想到了一个好主意：让你做！因此，你需要代替 jy123 完成这个艰巨的任务，如果没有，那你就做好跑圈的准备吧。

输入

第一行两个数，$t$ 和 $n$

第二行有 $n$ 个数，每个数标识一种泡面的价格，注意：不保证数据的单调性

此后 $t$ 行，每行有两个数 $l, r$

输出

输出一共 $t$ 行，每行两个数，分别是 chxlong 想要的泡面和 lily 想要的泡面的价格。

样例

1 2
1 2
1 2

1 2