RPL_T2 - Take & Run

no tags 

 

 Take & Run is an important game of the Rainbowland Olympiads, consists in a large rectangle, in each grid of the rectangle there is a single natural number, every athlete takes their position and then the referee announces a random number (that is written on some grid of the large rectangle), all the athletes must search the number and when some of them find it, the athlete must return at full speed to the line to win.

 

Marge is questioning this game, she says that a pattern can be discovered as all the numbers are sorted along the rectangle grids, Marge wants to win the Olympiads, and the help of third persons is allowed in Rainbowland, she requests your help and she will give you all the numbers written on the grid of the rectangle, it is known that the number at [0,0] < [0,1] < … < [0,M] < [1,M] < … < [N,M]. Where the left number stands for the rows and the right one for the columns (the format is [R,C]).

 

INPUT:

The first line of the test data will start with an integer T representing the T test cases, then, an integer N and M will come, then, NxM numbers will follow, meaning that in the next N lines there will be M numbers representing the number located on the grid, after that, Q requests will come, each requests consist on a natural number P that exists somewhere over the rectangle.

 

OUTPUT:

You must output the string “Scenario #i:“, where i is the test case you are evaluating, a blank line, and then, the position [R,C] where the natural number given in the request is located.

 

Print a blank line between test cases

 

SAMPLE DATA:

 

INPUT

OUTPUT

2

3 3

1 2 3

4 5 6

7 8 9

2

5

4

3 4

298 388 641 642

643 644 645 646

777 888 998 999

2

999

644

Scenario #1:

2 2

2 1

 

Scenario #2:

3 4

2 2

 

CONSTRAINTS:

 

1 <= T <= 10

 

Small input (30%):

1 <= {N,M} <= 100

1 <= Number on the grid <= 10^9

1 <= Q <= 100

 

Large input (70%):

101 <= {N,M} <= 2000

1 <= Number on the grid <= 10^9

1 <= Q <= 10000

 

It is guaranteed that every number on the grid will be different from each other.



Added by:david_8k
Date:2012-06-19
Time limit:0.100s-0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem used for the RPL Warm-up session