Sequence query

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Given a sequence of  N positive numbers,and M queries 

A query maybe :

1 x,find the Maximun "weight" of the consecutive subsequence whose length >= x

2 x,  find the Minimum length of the consecutive subsequence whose weight >= x

the weight of a consecutive subsequence Seq:weight(Seq) = length of Seq * minimum number in Seq.

Input

The first line is an integer T(1<=T<=100) ,the number of test cases;

For each test case,

the first line contains two integer N,M(1<=N,M<=100000)

the second line contains N positive integers(all between [1,2^31-1])

The following M lines contains queries as descripted above, all number is within signed ilong long

any subsequences should not be empty(length >= 1)

Output

for each query,output a line contains an answer you find,if the answer doesn't exist,output -1

Sample Input

1 
2 2
1 2
1 2
2 1

Sample Output

2
1

Source

dream

Manager

Information
Solved Number60
Submit Number524
Problem Tags
data structures
dp
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel