Pathfinding in a Grid

You are given a grid with r rows and c columns. Each cell in the grid contains either a 1 (accessible cell) or a 0 (blocked cell). Your task is to determine if there exists a path from the top-left cell (first row, first column) to the bottom-right cell (last row, last column). You may only move either right or down at each step.

If such a path exists, output the sequence of moves as a string consisting only of the characters R (for right) and D (for down). If multiple valid paths exist, output the one found by a depth-first search that first tries moving right and then down. If the grid consists of a single cell which is accessible, output an empty string (since no moves are required). If no valid path exists, print NO PATH.

Note: The movement restrictions imply that from any cell at position \((i,j)\), you can move to \((i,j+1)\) or \((i+1,j)\) provided the cell is accessible (i.e. its value is 1). The recursive decision process can be represented using the following recurrence relation:

[ \text{path}(i,j)= \begin{cases} \text{Empty String} & \text{if } i = r-1 \text{ and } j = c-1 \ R + \text{path}(i,j+1) & \text{if } j+1 < c \text{ and } grid[i][j+1] = 1 \ D + \text{path}(i+1,j) & \text{if } i+1 < r \text{ and } grid[i+1][j] = 1 \ \text{NO PATH} & \text{otherwise} \end{cases} ]

inputFormat

The first line of input contains two integers r and c separated by a space, representing the number of rows and columns respectively.

The next r lines each contain c integers (either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single line. If a valid path exists, print the path as a sequence of characters 'R' and 'D'. If the grid is a single accessible cell, print an empty line. Otherwise, if no path exists, output NO PATH.

## sample

3 3
1 0 0
1 1 0
0 1 1

DRDR

</p>