其实你们都不知道，小B是很小气的。一天小B带着他的弟弟小B'一起去摘果子，走着走着，他们忽然发现了一颗长满了果子的树。由于弟弟长得太矮了，弟弟只有让哥哥小B帮他摘一些果子下来。哥哥小B说:"弟弟啊，不是我不想给你摘多，我只是一次拿不了那么多，昨天晚上又没睡好，只能上一次树。所以哥哥只能给你摘一个哈。"没办法，弟弟只有答应了这个要求。 于是几下小B就上了树，树上的果子还真多，有N个呢！！但是小B很快发现这些果子大小不一。抠门的小B就想给自己拿个最大的，给弟弟拿个最小的果子。但是由于树上有些果子太高，小B不一定可以够着，所以他给你选了P个可以够着的果子区间，让你在这些区间里面找一个最大的果子和一个最小的果子。

共p+2行， 第一行为n和p， 第二行为区间[1,n]的果子大小（用正整数表示） 后面p行形如a b，意为每次询问的区间的左界和右界

共p行，第i行为第i次询问时得到的最大值以及最小值（一个询问用空格空开max和min） 【注意】在输入数据中果子的大小是无序的。

5 2
1 3 2 4 5
1 4
2 5

4 1
5 2