Description
NTHU is a kingdom, housing students and various creatures, those creatures like Procat (破貓), Crazytingyaobeast (瘋狂挺腰獸), Koprofessor (摳腳獸), EmperorPenguin07 (皇帝企鵝7號), FatFatCat (胖胖貓), Thankshanger (謝衣架), and more. We refer to these creatures as “Pokemon” because they are cute and unique in their own way.
One day, a Pokemon snake, though it does not consider itself a Pokemon ^^, has escaped!
Recently, several computer science students have found the snake near the 新齋.
Our snake-catching team leader (捕蛇大隊長), Thanksone, volunteered to capture the snake. He prepared to go with a wooden stick and a blue laundry basket.
[Thanksone is ready to catch the snake]
However, Koying thought this was too dangerous and decided to lend the road roller to Thanksone, allowing him to use it to crush the snake.
Once Thanksone got hold of the road roller, he became very excited and embarked on numerous modifications to the machine. These modifications were aimed at making it easier for him to capture the snake.
[Simulation environment]: In order to test whether the modified road roller could successfully crush the snake, Thanksone designed a simulation environment.
- There is an N x M grid map, representing the campus of NTHU.
- Each grid cell in row i and column j on the map contains a unique Pokemon Value Pi, j, representing the frequency of appearance of a Pokemon at the cell.
- All creatures within NTHU, including the snake and Thanksone, will not leave the campus.
[Snake's movement]: Since the snake doesn't consider itself a Pokemon, it will start from the grid with the lowest Pokemon Value.
- The snake moves one grid in one second, and its movement does not consume any energy.
- The snake initially faces to the right, and it will try to move in the direction it is currently facing.
If it can't move in that direction, it will switch its facing direction, that is right to left or left to right. This change of direction happens instantly and doesn't consume any time.
For example
The snake keeps moving until it is crushed by the road roller or the road roller runs out of fuel.
[Road roller's movement]: On the other hand, since Thanksone thinks that the snake is also a Pokemon, he will start the road roller from the grid with the highest Pokemon Value.
- The road roller moves one grid in one second, and each grid movement consumes one unit of fuel. The road roller can move in eight directions (up, down, left, right, up-left, up-right, down-left, down-right).
- In particular, the road roller periodically emits searchlights (探照燈) in all eight directions (up, down, left, right, up-left, up-right, down-left, down-right), searching for the snake. These searchlights extend in those directions until they are blocked.
- If a searchlight illuminates the snake, the road roller will move in the direction of (Snakex, Snakey), where (Snakex, Snakey) is the current location of the snake. It will move one grid at a time, repeatedly, until it reaches the position (Snakex, Snakey) or runs out of fuel.
For example:
- If no searchlights illuminate the snake, the road roller will teleport (傳送) in one second to the grid which has not been visited and is with the closest Pokemon Value to the current grid's Pokemon Value. (If there are multiple such grids, move to the one with the lowest Pokemon Value.) (Guarantees that there is at least a grid available for teleportation.)
For example:
- After the teleportation is completed or upon reaching (Snakex, Snakey), the road roller will emits searchlights again.
- If a searchlight illuminates the snake, the road roller will move in the direction of (Snakex, Snakey), where (Snakex, Snakey) is the current location of the snake. It will move one grid at a time, repeatedly, until it reaches the position (Snakex, Snakey) or runs out of fuel.
The road roller keeps moving following the policy in Step 2 until it runs out of fuel or the snake is successfully crushed.
We define the road roller crushing the snake as the snake and the road roller being on the same grid at the same time.
When the road roller comes to a stop, please output how much fuel is remaining.
- If the road roller successfully crushes the snake, also output "Gotcha!" (without quotes).
- Otherwise, also output "NO Snake QQ~" (without quotes).
Input
The first line consists of three positive integers, N, M, and S, indicating that the map size is N x M, and the initial fuel level of the road roller is S.
Following that, there are N lines, each containing M positive integers, denoted as Pi, j, representing the Pokemon Value for the grid cell in row i and column j.
Constraints
- Test Cases 1 ~ 3: N = 1
- Test Cases 4 ~ 6: 1 ≤ N ≤ 102
- For all test cases: 2 ≤ M ≤ 102, 1 ≤ S ≤ N * M, 1 ≤ Pi, j ≤ 10000
- It is guaranteed that no two grid cells have the same Pokemon Value.
Output
In the first line, please output an integer, representing the remaining fuel of the road roller.
In the second line:
- if the road roller successfully crushes the snake, output "Gotcha!" (without quotes).
- if the snake is not crushed by the road roller, output "NO Snake QQ~" (without quotes).
Remember to print a ‘\n’ at the end of the output.
Sample IO Description
Sample I/O 1:
1. The road roller emits searchlights (探照燈) in all eight directions.
2. A searchlight illuminates the snake and the snake is at (3, 3), so the road roller decided to go to (3, 3).
Since the snake can't go right, it switches to facing the left.
3. The road roller goes 1 step on the right-down direction and takes 1 unit of fuel, with 6 units of fuel left.
The snake goes 1 step on the left direction.
4. The road roller goes 1 step on the right-down direction and takes 1 unit of fuel, with 5 units of fuel left.
The snake goes 1 step on the left direction.
5. Since the road roller reaches (3, 3), it emits searchlights in all eight directions again.
6. A searchlight illuminates the snake and the snake is at (3, 1), so the road roller decided to go to (3, 1).
Since the snake can't go left, it switches to facing the right.
7. The road roller goes 1 step on the left direction and takes 1 unit of fuel, with 4 units of fuel left.
The snake goes 1 step on the right direction.
The snake met the road roller at (3, 2) and the road roller has 4 units of fuel left, so Thanksone stops road rolling.
Sample I/O 2:
1. The road roller emits searchlights (探照燈) in all eight directions.
2. No searchlights illuminate the snake, so the road roller will teleport to the grid with the closest Pokemon Value to 95 and has not been visited. (If there are multiple such grids, move to the one with the lowest Pokemon Value.)
So the road roller teleports to 91, which costs 1 unit of fuel, with 3 units of fuel left.
The snake goes 1 step on the right direction.
3. The road roller emits searchlights (探照燈) in all eight directions.
4. A searchlight illuminates the snake and the snake is at (3, 3), so the road roller decided to go to (3, 3).
Since the snake can't go right, it switches to facing the left.
5. The road roller goes 1 step on the right direction and takes 1 unit of fuel, with 2 units of fuel left.
The snake goes 1 step on the left direction.
The snake met the road roller at (3, 2) and the road roller has 2 units of fuel left, so Thanksone stops road rolling.
