Reachability in a Height-Constrained Grid

In this problem, you are given a grid representing a landscape with integer heights. Your task is to determine if there exists a path from the top-left cell ( (0,0) ) to the bottom-right cell ( (N-1, M-1) ) such that the absolute difference between the heights of any two consecutive cells on the path is at most ( K ). In other words, if ( G_{i,j} ) represents the grid, then for every two consecutive cells ( (x_1, y_1) ) and ( (x_2, y_2) ) on the path, it must hold that: [ |G_{x_1,y_1} - G_{x_2,y_2}| \le K ] You can move in the four cardinal directions: up, down, left, and right. Print "Reachable" if such a path exists; otherwise, print "Not reachable".

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains a single integer ( T ) indicating the number of test cases. For each test case:

• The first line contains three integers ( N ), ( M ), and ( K ), where ( N ) and ( M ) are the number of rows and columns of the grid respectively, and ( K ) is the maximum allowed difference in height between adjacent cells.
• The next ( N ) lines each contain ( M ) space-separated integers representing the grid.

outputFormat

For each test case, output a single line via standard output (stdout) containing either "Reachable" if a valid path exists from the top-left cell to the bottom-right cell, or "Not reachable" otherwise.## sample

3
3 3 2
0 2 3
1 1 2
4 3 0
4 4 1
0 3 5 6
1 2 7 8
2 3 6 9
0 1 1 1
2 2 1
1 3
2 1

Reachable
Not reachable
Reachable