题目描述

小 YLM 和小 LYA 是好朋友，他们最喜欢玩的就是把地上的几桶水搬来搬去。有一天，小 YLM 突发奇想，询问 LYA 让他在其中一部分水桶中，找出最重的水桶编号并求出这堆水桶的总重量。

输入格式

共 2+m 行，第一行包含两个整数 n , m 。表示水桶的个数和询问的个数。

第 2 行包含 n 个数 $a_i$ ，表示第 i 个桶的重量。

接下来 m 行，每行包括两个数 l , r 。表示询问水桶的区间。（即在编号为 l 到编号为 r 的区间询问，如果有多个最大的水桶，输出排在最后面的水桶编号）。

数据范围

0 <= n <= 10000

0 <= m <= 1000

0 <= $a_i$ <= 2*$10^6$

0 <= r-l+1 <= 10000

输出格式

共m行，每行包括两个数，即最重水桶的编号和当前区间水桶的总重量。

样例

5 2
1 2 3 4 5
1 3
2 4

3 6
4 9