L. Lawn Stripes
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lawn stripes are drawn using a roller to flatten grass blades in a particular direction and impart a sheen that, at a distance, is distinguishable from blades flattened in another direction. This is typically for aesthetic appeal.

We are going to draw lawn stripes in our square garden using a roller in any of the $$$4$$$ cardinal directions. The roller must stay on the lawn throughout. The final direction of a piece of lawn is determined by the last time the roller ran over it, including starting from or finishing there.

Illustration of Sample Input 1.

Given a description of the lawn and the starting point of the roller, determine how to draw the pattern.

Input
  • The first line of input contains the width and depth in metres of the lawn, $$$n$$$ ($$$1 \le n \le 100$$$)

  • The second line of input contains the row and column of the roller, $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le n$$$).

  • Each of the next $$$n$$$ lines contains $$$n$$$ characters from (l|r|u|d) giving the desired direction of a square metre of lawn.
Output

If it is not possible to draw the pattern, output impossible. Otherwise, demonstrate a solution in under $$$10n^2$$$ moves by outputting the number of moves to use on one line, followed by the moves on the remaining lines.

Each move consists of a distance in metres $$$d$$$ and a direction from (l|r|u|d). A roller following the instructions must roll over every square metre without leaving the lawn.

Examples
Input
4
1 4
rrrd
llll
rrru
ulll
Output
8
3 l
3 r
3 d
3 l
1 u
3 r
1 u
3 l
Input
2
1 1
rd
ul
Output
impossible