Do You Have a Problem with Insung??

Interview

Time limit1sMemory limit512 MB

Summary

On an H by W grid with obstacles of varying height, decide if Insung can reach the goal, given that each move costs 1 strength and climbing to a higher cell costs extra strength equal to the height difference.

Level: Medium5 of 10
Topics: BFS, Graph, Simulation, Implementation
Solved: No attempts yet

Problem

Insung joined the Insat special course to become popular. On the first day of training, Insung must reach the goal in a treacherous maze. If he fails to get through the maze within the time limit, Instructor Myeonggi will curse at him, so Insung tries his best to get through the maze.

The maze is a grid of width $W$ and height $H$ , and Insung can move one cell up, down, left, or right on the grid per move. Each time a move is completed, Insung's remaining strength decreases by 1, and once the remaining strength becomes 0 or less, he can no longer move.

Each cell of the maze may contain an obstacle, and each obstacle has a height. Every location without an obstacle has height 0. When Insung moves, if the height of the destination is lower than the height of his current location, he can move with no restriction. When moving to a higher place, he can jump, and the height he must jump is (height of the destination - height of the current location). If his remaining strength is greater than or equal to the height he must jump, he can move; otherwise, he cannot move.

Can Insung overcome his physical limits, reach the goal safely, and avoid being cursed at by Instructor Myeonggi?

Input

The first line gives the number of test cases $T$ . Each test case is given as follows.

The first line gives the maze's height $H$ , width $W$ , number of obstacles $O$ , initial strength $F$ , the start coordinates $X_s$ (row), $Y_s$ (column), and the goal coordinates $X_e$ (row), $Y_e$ (column).

From the second line, $O$ lines give the coordinates $X$ (row), $Y$ (column) and height $L$ of each obstacle. All obstacles are at distinct locations.

Output

For each of the $T$ lines, print "잘했어!!" if Insung can reach the goal, and "인성 문제있어??" if he cannot reach the goal.

Constraints

$1 \le T \le 10$
$2 \le H, W \le 100$
$0 \le O \le H \times W$
$0 \le F \le 10{,}000$ , $F$ is an integer.
$1 \le L \le 50$ , $L$ is an integer.
$1 \le X, X_s, X_e \le H$
$1 \le Y, Y_s, Y_e \le W$
The start and goal positions have no obstacle.

Examples2

Example 1

Input

1
3 3 7 5 1 1 3 3
1 2 4
1 3 8
2 1 1
2 2 2
2 3 4
3 1 8
3 2 4

Expected output

잘했어!!

Example 2

Input

1
3 5 3 6 1 1 3 5
1 2 8
2 1 8
3 1 4

Expected output

인성 문제있어??