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. $($In this case, the availability of oxygen need not be considered$)$

$-$ the feasible path$/$paths along with remaining oxygen level.

Note : Paths in which a diver has sufficient oxygen when he reaches the destination are considered as feasible paths.

If there is no path to reach the destination pool, then print $"$No path available to reach the destination".

If there are no feasible paths available, then print $"$No feasible path".

Note : When you click on "Compile & Run", you have to provide the input and check if you get the expected output.

Either you can provide the input directly or you can copy paste the sample input from the problem description. Then click on clipboard option as shown below. In the clipboard window paste the copied text in the "Paste section" and click the "Paste button". The text will appear in your console. You can just press "Enter" and see the output.

Sample Input $1$:

$4$

$3561$

$4093$

$8760$

$9554$

$35$

Sample Output $1$:

The available paths are

RRR

RRDRU

RRDDDR

RRDDLDRR

RRDDLLDRRR

DDRRDR

DDRRURU

DDRRUUR

DDRDRR

DDRDRUURU

DDRDRUUUR

DDDRRR

DDDRRUURU

DDDRRUUUR

DDDRURDR

DDDRURURU

DDDRURUUR

The feasible paths with remaining oxygen levels are

RRR $9$

RRDRU $19$

RRDDDR $0$

Explanation:

For the given input the available paths are

$(0,0),(0,1),(0,2),(0,3)$

$(0,0),(0,1),(0,2),(1,2),(1,3),(0,3)$

$(0,0),(0,1),(0,2),(1,2),(2,2),(3,2),(3,3)$

$(0,0),(0,1),(0,2),(1,2),(2,2),(2,1),(3,1),(3,2),(3,3)$

$(0,0),(0,1),(0,2),(1,2),(2,2),(2,1),(2,0),(3,0),(3,1),(3,2),(3,3)$

$(0,0),(1,0),(2,0),(2,1),(2,2),(3,2),(3,3)$

$(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,3),(0,3)$

$(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3)$

$(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$

$(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(2,2),(1,2),(1,3),(0,3)$

$(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(2,2),(1,2),(0,2),(0,3)$

$(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(3,3)$

$(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),(1,2),(1,3),(0,3)$

$(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),(1,2),(0,2),(0,3)$