Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dracarys

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


    Discussion
    Statistics

    75% Solution Ratio

    YouKnowWhoEarliest, 8M ago

    fire_tornadoFastest, 0.5s

    kishore03Lightest, 1.5 MB

    wajiulShortest, 734B

    Submit

    Login to submit