Minimum Path Difficulty

You are given an R x C grid of integers. Each cell in the grid represents a difficulty level. Your task is to find a path from the top-left cell (0,0) to the bottom-right cell (R-1,C-1) such that the difficulty of the path is minimized.

The difficulty of a path is defined as the maximum absolute difference between the values of any two consecutive cells along that path. Formally, if the path consists of cells \((i_0,j_0), (i_1,j_1), \dots, (i_k,j_k)\), then the difficulty of the path is given by:

[ D = \max_{0 \leq t < k} \left| grid[i_t][j_t] - grid[i_{t+1}][j_{t+1}] \right| ]

Your goal is to compute the minimum possible value of \(D\) over all possible paths from the start to the finish.

Note: Movements can be made in the four cardinal directions: up, down, left, and right.

inputFormat

The first line of input contains two integers R and C (the number of rows and columns of the grid, respectively).

The next R lines each contain C space-separated integers representing the grid values.

You can assume that R and C are positive and the grid values are integers.

outputFormat

Output a single integer representing the minimum possible maximum absolute difference between adjacent cells along any path from the top-left to the bottom-right of the grid.

## sample

3 3
8 4 7
6 1 3
2 9 5

4