Knight’s Lotus Path

Farmer John built a beautiful rectangular pond divided into \(M \times N\) cells (\(1 \le M,N \le 30\)). Each cell is either a sturdy lotus (L), a rock (R) or pure, blue water (.). Bessie the cow is practicing ballet. Standing on a lotus cell, she wants to jump to another lotus cell. However, she can only land on a lotus cell. She moves like a chess knight: each move is either one cell horizontally and two vertically, or two vertically and one horizontally. Up to 8 moves are possible from any cell.

Sometimes, Bessie cannot reach the target lotus because some necessary cells are water. Farmer John can add extra lotuses by converting water cells into lotus cells (note that he cannot convert rocks). He wants to add the minimum number of lotuses so that a path exists from the start to the target. Under this restriction, he then wants to know the minimum number of moves Bessie must take, and finally, the number of distinct shortest paths achieving that.

More formally, you are given an \(M\times N\) grid. Each cell is one of the following:

• L: lotus (already present)
• R: rock (impassable)
• .: water

Bessie may only stand on cells containing a lotus. She is initially on a lotus cell and the target cell is also a lotus. You may convert any water cell (\(\text{.}\)) into a lotus (at a cost of 1 per cell) but you cannot convert rock cells. The cost of a path is defined as a pair \((a, s)\) where \(a\) is the total number of water cells used in the path (each counted once, since a water cell needs to be converted only once) and \(s\) is the number of knight moves (steps) taken. We assume that an optimal path is one with the lexicographically minimum cost \((a, s)\) (i.e. minimize \(a\) first then \(s\)). Your task is to compute:

1. The minimum number of extra lotuses (water cells to be converted) needed;
2. The minimum number of moves required under that conversion;
3. The number of distinct paths that achieve that optimal pair \((a, s)\).

Note: You may assume that the optimal path is simple (i.e. does not visit any cell more than once) so that the conversion cost is simply the sum over cells used (with a water cell costing 1 and a lotus costing 0).

inputFormat

The input begins with two integers \(M\) and \(N\) (the number of rows and columns of the grid). Then follow \(M\) lines, each containing a string of length \(N\) consisting only of the characters L, R, and ., representing lotus, rock, and water respectively. It is guaranteed that the start and target positions are lotus cells.

The next line contains two integers \(r_s\) and \(c_s\) (1-indexed), specifying the starting cell.

The following line contains two integers \(r_t\) and \(c_t\) (1-indexed), specifying the target cell.

outputFormat

Output three space‐separated integers:

• the minimum number of water cells that must be converted to lotus,
• the minimum number of knight moves under that conversion,
• and the number of distinct optimal paths achieving that.

sample

4 4
LLLL
LLLL
LLLL
LLLL
1 1
4 4

0 2 2