Description

给定一个有N个整数组成的数列，有M个关于次数列的询问：

1 x　找出长度大于等于X的连续子序列中Weight值最大的序列，输出Weight值

2 x　找出所有Weight值大于等于x的连续子序列中长度最小的，输出长度值。

　　在这里，一个连续子序列的Weight值是这么计算的：Weight(seq) = Length(seq) * Minimum Value(seq)

Input

第一行输入一个T,代表一共有T组测试数据。
每组数据第一行输入两个正整数，N和M
第二行输入N个数，每个数的范围都是INT范围内的。
接下来的M行，每行都包含了一个上述的询问。（N,M <=100,000 ;T<=15）

Output

对于每组数据的每个询问，输出答案。没有答案输出-1.

Sample Input

1
2 2
1 2
1 2
2 1

Sample Output

2
1

HINT

其实都是极限数据。。

Source

The 9th NBU Programming Contest