RPLN - Negative Score

Orianna is a great swimmer and she's going to a swimming competition this month and needs your help as she is highly paranoic about the results of the competition.

The competition consists in some sort of evaluations, every judge makes a score and, based on that score and the score of other contestants she will get a score belonging to her results, those scores are final, meaning that will not change in the competition.

Orianna requires this solution with urgency, she is getting evaluated on a lot of ways and she is very worried about her results, so she wants to know what is the worst score from an evaluation A to other evaluation B inclusive.

Input

The first line of the test data will start with an integer T representing the T test cases, then, T cases will follow, each of the cases starts with two integers N and Q, denoting the number of evaluations Orianna had, then, N integers will follow denoting the score on each evaluation, after that, Q queries will begin, each query consist on two integers A and B.

Output

You must output the string “Scenario #i:“, a blank line and then the result of each query, remember, Orianna is interested on the worst score from evaluation A to evaluation B inclusive.

Example

Input:
2
5 3
1 2 3 4 5
1 5
1 3
2 4
5 3
1 -2 -4 3 -5
1 5
1 3
2 4

Output:
Scenario #1:
1
1
2
Scenario #2:
-5
-4
-4

Constraints

  • 1 <= T <= 100

Small input (30%):

  • 1 <= N <= 1,000
  • 1 <= Q <= 1,000
  • -10^9 <= Ni <= 10^9
  • 1 <= A <= B <= N

Large input (70%):

  • 1 <= N <= 100,000
  • 1 <= Q <= 100,000
  • -10^9 <= Ni <= 10^9
  • 1 <= A <= B <= N

Solutions rejudged due to weak test cases.


Added by:david_8k
Date:2012-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem used for the RPL contest

hide comments
2012-06-26 23:26:10 Jared Deckard
@sigsegv: More than one round of judging. You get 5s for each.
2012-06-26 14:52:26 MyTh
time limit is 5 sec then why my 15 sec sol. is AC?? cn anybody explain??
2012-06-26 11:43:51 Anshul Gupta
Need some tricky test cases
@David : please look into my solution (7215184) , getting WA , tested on lot of test cases
2012-06-26 00:49:50 Himanshu Srivastava
why my code is failing at testcase 9.....any tricky test case ? :( :(
AC :)
precison errors !!

Last edit: 2012-06-25 14:47:36
2012-06-26 00:49:50 Nnavneetsinha
order stats is enough or do we need dynamic order stats for this problem??
2012-06-26 00:49:50 unXled
got AC using another approach but very weird getting TLE using tree and the thing i mentioned in my previous comment....
but relaxed now....this ques took my 2 hours....need a break nw....

Last edit: 2012-06-24 13:44:05
2012-06-26 00:49:50 unXled
changing scanf to cin gives tle nd with scanf getting SIGSEGV....whats happening????
@problem setter: plz look into my submission and help me....
2012-06-26 00:49:50 unXled
getting SIGSEGV....dont know why????
2012-06-26 00:49:50 redbustar
Keep on getting WA ...any tricky test cases??
AC :)

Last edit: 2012-06-24 19:26:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.