Description

输入一串数字，给你M个询问，每次询问就给你两个数字 X,Y,要求你说出X到Y这段区间内的最大数。

Format

Input

第一行有2个整数n,m。分别表示n个数和m个询问，接下来一行为N个数。接下来M行，每行都是两个整数 X,Y。

Output

输出共M行，每行输出一个数。

Sample 1

Input

10 2
3 2 4 5 6 8 1 2 9 7
1 4 
3 8

Output

5
8

Limitation

1s, 64MiB for each test case.