On his trip to Japan, Milan wanted to try his chances at pachinko — a Japanese game that can be likened to a vertical game of pinball. By turning a knob, you can control the strength at which you shoot small metal balls into the machine. These metal balls fall down columns and bounce off obstacles until they fall into a gate, with the gate into which your ball falls determining your winnings.

Previously, Milan was struggling to win until his friend, Paul, told him the expected winnings of each column. With this in mind, Milan was able to strategically turn the knob just right so that he could get the metal balls into his desired column. He was slowly winning some, but still making a net loss.

Just as he has thoughts of giving up, Paul comes back around.

"Uh, so I forgot to account for the obstacles earlier", he says, as he pats Milan on the shoulder.

"Oh what? Come on man!" sighs Milan as he stares as his last ~100~ yen.

Paul explains that the pachinko machine can be modeled as follows: you can drop the ball in any column and it falls down until it either reaches the bottom of the machine (which results in no wins), a gate (indicated by a number ~1~ to ~9~, which results in that win), or an obstacle (indicated by an asterisk). If a ball hits an obstacle, it proceeds falling in the column to the left or to the right of the obstacle, with ~50/50~ probability. No two obstacles or gates are adjacent, not even diagonally, and none are located in the leftmost or rightmost column.

To maximise his expected winnings, which column should Milan aim to get his balls into?

Input

The first line contains two integers ~h~ and ~w~ ~(1 \leq h, w \leq 1000)~, the width and height of the pachinko machine.

The next ~h~ lines contain ~w~ characters describing the pachinko machine, with . denoting an empty space, * denoting an obstacle, and ~1~ through to ~9~ denoting the winning gates.

Output

On the first line, output the maximal expected winnings with either an absolute or a relative error of at most ~10^{-6}~.

On the second line, output a single integer, the column with the maximum expected winnings. The column is ~1~-indexed.

Clarifications

• You are guaranteed to get a non-zero maximal expected value.

Example

Input 1

7 5
.....
.1...
...2.
.*...
.....
.....
..5..

Output 1

5.0000000
3

In this case, the optimal column that Milan should aim for is column ~3~ (~1~-indexed). Since there are no obstacles in the way, he can go straight for this column, which has a maximal expected value of ~5~.

Input 2

8 8
...1....
........
..*...*.
....*...
.1......
...*.*..
........
..9.7.7.

Output 2

7.5000000
5

If we choose column ~5~, we encounter a first obstacle which has a ~50/50~ probability of going left or right. Then, we encounter an obstacle on either side, which splits the probabilities once again. Then, we reach either the gates that have ~9~, ~7~ or ~7~.

The probability of getting these gates (given the previously encountered obstacles) are ~0.25~, ~0.5~, and ~0.25~ respectively. Using this, we can calculate the maximal expected winnings as follows:

$$\displaystyle 9 \times 0.25 + 7 \times 0.5 + 7 \times 0.25 = 7.5$$

Hence ~7.5~ is our maximal expected winnings and column ~5~ is what Milan should choose.

Input 3

10 10
.*.*.*.*..
..........
..*.*.*.*.
..........
.*.*.*.*..
..........
..*.*.*.*.
..........
.*.*.*.*..
....9.....

Output 3

3.3750000
5