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
 Lang: Pascal fpc 3.0.0C gcc 6.3.1C99 gcc 6.3.1C++98 gcc 6.3.1C++11 gcc 6.3.1C++14 gcc 6.3.1Java gcc-gcj 6.3.1 Source:
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.4 (15 votes) Quality: 4.8 (13 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 