RPL_T2 - Take & Run
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 |