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.
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.
For i-th case, print “Case #i:”. In the next Q lines print results of Q queries.
Input | Output |
---|---|
1 5 3 3 1 4 2 5 1 2 1 3 5 5 | Case #1: 3 4 5 |