# 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