Divers Club is an international sports training academy. They would like to train their new scuba diving trainees for an upcoming competition. Focussing on underwater scuba diving, the club created an artificial deep pool interconnected with tunnels on adjacent sides, so that the trainees can dive and get trained for underwater diving. These pool setups are considered as an NxN matrix. A diver can move in any of the four directions $($say: right, down, up$,$ left$)$ but not diagonally. Also as the game takes place underwater, divers will be provided with an oxygen cylinder. Divers should start from the starting pool and reach the destination pool without entering the restricted pools and without losing their life.Pool Info :

$-$ Each pool detail is mentioned in numbers

$-$ The pools which are mentioned as $"0"$ are restricted to enter.

$-$ Oxygen refilling pumps are available in pools numbered $"9".$

Rules for Playing

$-$ The top left pool is the starting point.

$-$ The destination point is either the top right corner or the bottom right corner of the pool.

$-$ A diver can move in any of the four directions $($say: right, down, up$,$ left$)$ but not diagonally.

$-$ Divers will be equipped with an oxygen cylinder with $"$M$"$ capacity.

$-$ While swimming from a pool with a value $"$AX$"$ to a pool with a value $"$Ay$",$ there will be an oxygen consumption of $"$AX$+$Ay$".($See the explanation given below for more clarity$)$

$-$ In a few cases, the oxygen capacity may not be sufficient. If a diver reaches pool $"9"$ with sufficient oxygen, then the oxygen will be refilled and will attain the capacity $"$M$".$

Input Format:

The first line represents the value of n$.$

The next n lines input represents the underwater pool details as n$*$n matrix.

The last input is the oxygen capacity $"$M$".$

Output Format:

The output should display the following:

$-$ all the available paths to reach the destination pool without touching the restricted pool. program in java