Grid Journey

You are given an n x n grid, and your task is to find all the paths that lead from the top left corner to the bottom right corner of the grid.
In the grid, you can only move down or right. Each cell represents a position in the grid, and it is either empty or blocked. You cannot traverse through blocked cells. Your goal is to find all possible paths from the top left corner to the bottom right corner by moving only down or right.

Input

The first line consists of a single integer n (1 ≀ n ≀ 10), representing the size of the grid. The next n lines contain n space-separated integers, either 0 (empty) or 1 (blocked), representing the grid cells.

Output

Print all the paths from the top left corner to the bottom right corner, considering only the empty cells. Each path should be printed on a new line. Each path is represented by a sequence of characters D (for moving down) and R (for moving right). You can output the paths in any order.

Examples

Input
Output
3 0 0 1 0 0 0 0 1 0
RDRD DRRD
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue