Domino Tiling

In this problem, you have to transform one domino tiling of a rectangle into another by moving dominoes along cycles.

Consider a rectangular grid of size h × w. A domino piece (or simply domino) is a rectangular block that can be placed on any two cells of the grid sharing a common side. A tiling of the grid is a collection of domino pieces such that each cell of the grid is covered by exactly one piece in the collection. Note that dominoes may not cross the border of the grid.

You are given two tilings of the grid: initial tiling and target tiling. Your task is to transform initial tiling into target tiling. In order to achieve that, you are allowed to make moves. A single move consists in picking a domino cycle and moving dominoes along that cycle (the formal definition is given below). The cost of each move is the number of cells in the respective domino cycle. The total cost of transformation is the sum of costs of all moves you make. Of course, the total cost must be minimal possible.

Now, to the details.

Let us define a domino cycle of positive length n on a given tiling. Consider a circular sequence of 2n distinct cells such that any two consecutive cells in the sequence share a common side. Here, circular means that the first and last cells of the sequence are also considered consecutive. Obviously, there are 2n pairs of consecutive cells in such a sequence. Cover n of them by n non-overlapping domino pieces and you get a domino cycle.

The process of moving dominoes along a cycle results in change of the tiling. First, the n domino pieces covering all the 2n cells which belong to the cycle are removed. After that, n new non-overlapping domino pieces are added to cover n other pairs of consecutive cells. One can easily see that the resulting collection of pieces is also a tiling. Recall that the cost of such move is 2n.

Input

The first line contains two integers h and w separated by a space: height and width of the rectangular grid (1 ≤ h, w ≤ 100).

The next h lines contain w characters each and describe initial tiling. Each of these characters is one of the following:

• character “l” denotes a left part of a domino piece,

• character “r” denotes a right part of a piece,

• character “u” denotes an upper part, and

• character “d” corresponds to a lower part.

Next goes a line containing w dash signs (“-”).

The next h lines contain w characters each and describe target tiling in the same fashion.

It is guaranteed that the input is consistent:

• h and w are chosen in such a way that tiling an h× w grid is possible

• each character in each tiling is guaranteed to have the required neighbor in the required direction.

Output

On the first line write two integers separated by a space: m, the number of moves, and p, the total cost of transformation. Note that as long as the cost p is minimal possible, the number of moves m can be arbitrary.

The next m lines should describe the moves, one per line. A move along a domino cycle of k cells should be written as k r_1 c_1 r_2 c_2 ... r_k c_k. Here, r_i and c_i are the coordinates of i-th cell of the cycle. Separate consecutive tokens on a line by one or more spaces. You can start a cycle at any point and traverse it in any direction.

Examples

Note

In the first example, the minimal total cost is 10. It can be achieved by just one move which involves the 10 border cells of the grid in cyclic order. Five dominoes covering cells (1, 1) and (1, 2), (1, 3) and (1, 4), (2, 4) and (3, 4), (3, 3) and (3, 2), (3, 1) and (2, 1) are removed. After that, new dominoes covering cells (1, 2) and (1, 3), (1, 4) and (2, 4), (3, 4) and (3, 3), (3, 2) and (3, 1), (2, 1) and (1, 1) are added.

The answer is illustrated below on the left. Note that there could be other ways of achieving the target tiling. To the right is another solution which is however not optimal.

In the second example, the minimal total cost is 12. It can be achieved by moving the dominoes along three small cycles each of which contains four cells. The process is illustrated below.