Tasks:
 
Task DescriptionDiscussion (0)
Task :: z-board
Little Z is playing a game. Game is consisted of a coin and a rectangular board of r rows and c columns. In order to explain game, we will consider that position (A, B) to refer to the field at row A and column B.
At the beginning of the game, the coin is placed at position (1, 1). The goal of the game is to move the coin to position (r, c). From position (x, y), the coin can be moved to position (x + 1, y), labeling with an upper-case letter 'D', or (x, y + 1), labeling with an upper-case letter 'R'. However, some fields of the board are broken and coin can't be placed on these fields. To make the game even harder, Little Z has to find K-th lexicographically smallest sequence of moves which will get the coin from the position (1, 1) to the position (r, c).
Sequence of moves is represented with letters 'D' and 'R', where i-th letter represents i-th move.

Be a kind friend, as Little Z is, and help him to find described path.

INPUT:
The first line of the standard input contains three space-separated integers cardinals r, c (2 <= r, c <= 500) and K (1 <= K <= 10<sup>9</sup>). Each of the next r lines contain c characters. Each character is either '.', representing field on which the coin could be moved, or '#', representing broken field. j-th character at i-th line represents field at the position (i, j).

OUTPUT:
On the standard output you should print K-th path, if it exists, or "impossible" if it does not exist.

Input:
4 4 5
....
....
....
....

Output:
DRDDRR


Explanation:
5-th path is (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4).

Input:
4 5 11
....#
.....
.##..
.....

Output:
RRRDDDR


Explanation:
11-th path is (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) -> (2, 4) -> (3, 4) -> (4, 4) -> (4, 5).

Input:
5 5 51
.....
.....
.....
.....
.....

Output:
RDRDRRDD



Input:
2 2 3
..
..

Output:
impossible


Explanation:
There are only 2 possible sequences of moves - DR and RD.
Submit Solution
:
:
Available Languages
Task info
Name:z-board
Time:0.05 sec.
Memory:8 MB
#Tests:50
AddedBy: boba5551
Source:Slobodan Mitrović
Task Ratings
Difficulty:

4.6 (14 votes)
Quality:

4.9 (12 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
nbasic 0.054 s.
ortschun 0.057 s.
RobertGerbicz 0.06 s.
tjhance 0.063 s.
Mr.Ra16bit 0.063 s.
carlosjoa 0.065 s.
moshiur 0.066 s.
neal_wu 0.068 s.
halil 0.068 s.
_qwAker_ 0.069 s.
Solved By