Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

graphs

shortest paths

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Anti-Tetris

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputLet us consider the game "Sticky Tetris". In this game, there is a field of $$$n \times m$$$ squares. Tiles appear on the field and the player can move the tiles.

Each tile is a $$$4$$$-connected set of at most $$$7$$$ squares.

Each new tile appears in any position that fits inside the field, does not intersect any other tile, and the top cell of the tile is at the top row of the field. The player can move the tile left, right, and down, and at any moment the tile must still entirely fit inside the field and must not intersect other tiles. The player can stop the tile at any position at any time. After that, it cannot be moved. Since this is "Sticky Tetris," the tile will not fall once stopped.

You are given a final configuration of a "Sticky Tetris" game. You need to restore a sequence of steps that leads to that configuration if it exists.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 50$$$) — the size of the playing field.

The next $$$n$$$ lines contain a string of $$$m$$$ characters each. Each character could be either a '.', or lowercase English letter. Connected components of the same letter correspond to a single tile. Each tile consists of at most $$$7$$$ squares.

Output

If there is no solution, print $$$-1$$$.

Otherwise, print $$$k$$$ — the number of different tiles that are placed on the field.

On the next $$$k$$$ lines print the sequence of steps for each of the tiles in the order they are placed.

Each line consists of a number $$$x$$$ followed by a string with steps. $$$x$$$ ($$$1 \le x \le m$$$) is the starting column of the leftmost square in the top row of the tile. The string consists of characters 'L' (for left), 'R' (for right), and 'D' (for down), describing the path of that tile, ending with a single character 'S' (for stop). The final position of the tile determines which tile is being placed. The string with steps can have at most $$$n \cdot m + 1$$$ characters.

Examples

Input

3 2 aa ab aa

Output

2 2 DS 1 S

Input

5 6 ....dd .ccccd .cbbdd .aab.a aabbaa

Output

5 2 DDDS 4 DDLS 6 DDDS 2 DS 5 S

Input

5 3 ... aab abb aab .bb

Output

-1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2024 17:32:23 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|