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.


hide comments
||N0VICE||: 2014-07-29 15:43:55

first problem solved using segment trees :)
use of scanf,printf is recommended

Last edit: 2014-07-29 15:44:31
aristofanis: 2013-11-18 18:13:49

@RAHUL, @Krypt Pen, I think that WA is sent after your program is tested is all test cases, so you cannot be sure that it is failing at the 9th test case...

Gitu: 2013-09-19 06:17:59

The question taught me that (l+r)/2 is calculated slower than (l+r)>>1

Smit Mehta: 2013-08-30 10:34:57

Use fast I/O for 9th case.

govihuu: 2013-08-15 03:07:59

same algorithm C++ accepted, python runtime error (NZEC). I think input isn't orderliness.

Aditya Gourav: 2013-06-27 06:07:01

cake-walk :D

Ankur: 2013-05-22 12:55:09

@Neo - thanks !!
Your @Runtime comment got me AC :)

Federico Lebrón: 2013-05-20 04:56:42

No need for a 1M sized array, but be careful, I had several SIGSEGVs because I only read the input constraints, and stopped at the "small input" part - I didn't see there was the (not usual) "large input" description - entirely my fault. :)

Utkarsh Shahdeo: 2013-05-18 03:13:02

Segment tree works fine...

BLANKRK: 2013-05-15 12:44:25

finly done....... :D


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