Limits 1s, 512 MB

Daenerys Targaryen is riding her dragon in a fight against the White Walkers and Wights. There are N Wights standing in a line facing the dragon. Each of them has different level of strength left in them. Daenerys wants to know maximum strength among some consecutive Wights. Write a program to help her in that.

Input

First line of the input contains the number of test cases T (1 <= T <= 100). Then follows input for T test cases. Each test case contains the total number of Wights N (1 <= N <= 10^5) and number of Daenerys’ queries Q (1 <= Q <= 10^5). The next line contains N integers. The i-th integer Ai (1 <= Ai <= 10^5) is the strength of the i-th Wight (1 <= i <= N). The following Q lines will contain two integers L, R (1 <= L <= R <= N). It means Daenerys wants to find maximum strength among Lth Wight to Rth Wight.

Output

For i-th case, print “Case #i:”. In the next Q lines print results of Q queries.

Sample

InputOutput
1
5 3
3 1 4 2 5
1 2
1 3
5 5
Case #1:
3
4
5

Submit

Login to submit.

Statistics

76% Solution Ratio
YouKnowWhoEarliest, Apr '19
AUSTBit_BlitzFastest, 0.3s
kishore03Lightest, 1.5 MB
wajiulShortest, 734B
Toph uses cookies. By continuing you agree to our Cookie Policy.