One morning when you woke up, it was in a springy labyrinth.

I don't know why I'm in such a strange place. You have the option of waiting for help here, but you know from experience that if you stay in a labyrinth like this for a long time, a gust of wind will surely blow you away. It was. However, the time until the gust blows cannot be judged. So you thought it was best to act to minimize the expected number of moves required to escape the labyrinth.

When I picked up an unidentified scroll that had fallen under my feet and read it as a trial, I happened to be able to perceive the entire map of the labyrinth. Furthermore, by drinking the grass that I happened to have, I was able to know the positions of all the traps. Apparently, there are no traps other than dangerous monsters and springs in this labyrinth.

This labyrinth is shaped like a rectangle with several types of tiles, for example:



.. ## g. #
* #. * #. #
...... #
* s # *. * #



".":floor. You can walk around freely on this.

"#":wall. You can't get inside the wall.

"S": Your first position. Below this tile is the floor.

"G": Stairs. If you ride on this tile, you have escaped from the labyrinth.

"*":Spring. If you ride on this tile, it will be randomly blown onto one of the floors (excluding stairs and spring tiles). The odds of being hit on each floor are all equal.

The type of tile is one of these five.

You can move one square at a time from the tile you are currently riding to an adjacent tile in either the up, down, left, or right direction. However, you cannot move to Naname.

Given a map of the labyrinth, find the expected number of moves required to escape the labyrinth if you take the best strategy. It is not included in the number of movements that is blown by the spring.



Input

W H
c11 c12 ... c1w
c21 c22 ... c2w
:::
ch1 ch2 ... ccw


On the first line of input, the integer W (3 ≤ W ≤ 500) and the integer H (3 ≤ H ≤ 500) are written in this order, separated by blanks. The integer W represents the width of the labyrinth, and the integer H represents the height of the labyrinth.

The following H line contains W letters (not blank delimiters) that represent the map of the labyrinth. The format of this part is as in the example given above. Note that "s" and "g" appear exactly once in the data. In addition, one square around the labyrinth is always surrounded by a wall.

In addition, in the given labyrinth, no matter how you move and how it is blown by the spring, you will fall into a state where you cannot escape even if you can arbitrarily set the floor to be blown by the spring. You can assume that there is no such thing.

Output

Output the expected number of moves to escape when you take the best strategy. The output may contain errors, but the relative error to the true value must be less than 10-9.

Examples

Input

8 6
########
#..##g.#
#*#.*#.#
#......#
#*s#*.*#
########


Output

5.857142857143


Input

8 6

..##g.#
*#.*#.#
......#
*s#*.*#


Output

5.857142857143


Input

21 11

*#*.*.*.*.*.*.*.*#*#
*#...............#*#
*#.#.#.#.#.#.#.#.#*#
.#.#.#.#.#.#.#.#.##
...................#
.#.#.#.#.#.#.#.#.##
s#.#.#.#.#.#.#.#.#g#
...................#
...................#


Output

20.000000000000


Input

9 8

...#*.*#
.*.#...#
...#*.*#

.s....g#
.*#.*..#


Output

5.000000000000

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
	(W, H) = map(int, readline().split())
	S = [readline().strip() for i in range(H)]
	R = [[0] * W for i in range(H)]
	P = []
	cnt = 0
	for i in range(H):
		Si = S[i]
		for j in range(W):
			if Si[j] == 's':
				sx = j
				sy = i
				R[i][j] = 1
				cnt += 1
			elif Si[j] == 'g':
				gx = j
				gy = i
			elif Si[j] == '*':
				P.append((j, i))
			elif Si[j] == '.':
				cnt += 1
				R[i][j] = 1
	dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
	INF = 10 ** 18
	dist1 = [[INF] * W for i in range(H)]
	que = deque(P)
	for (x, y) in P:
		dist1[y][x] = 0
	while que:
		(x, y) = que.popleft()
		c = dist1[y][x] + 1
		for (dx, dy) in dd:
			nx = x + dx
			ny = y + dy
			if S[ny][nx] in '*#' or dist1[ny][nx] != INF:
				continue
			dist1[ny][nx] = c
			que.append((nx, ny))
	dist2 = [[INF] * W for i in range(H)]
	que = deque([(gx, gy)])
	dist2[gy][gx] = 0
	while que:
		(x, y) = que.popleft()
		c = dist2[y][x] + 1
		for (dx, dy) in dd:
			nx = x + dx
			ny = y + dy
			if S[ny][nx] in '*#' or dist2[ny][nx] != INF:
				continue
			dist2[ny][nx] = c
			que.append((nx, ny))
	left = 0
	right = 10 ** 21
	BASE = 10 ** 9
	for i in range(71):
		mid = (left + right) // 2
		su = 0
		for i in range(H):
			for j in range(W):
				if not R[i][j]:
					continue
				su += min(dist1[i][j] * BASE + mid, dist2[i][j] * BASE)
		if mid * cnt > su:
			right = mid
		else:
			left = mid
	write('%.16f\n' % min(dist1[sy][sx] + left / BASE, dist2[sy][sx]))
solve()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def bs(f, mi, ma):
	st = time.time()
	mm = -1
	mi = fractions.Fraction(mi, 1)
	ma = fractions.Fraction(ma, 1)
	while ma > mi + eps:
		gt = time.time()
		mm = (ma + mi) / 2
		if gt - st > 35:
			return mm
		if isinstance(mm, float):
			tk = max(1, int(10 ** 15 / mm))
			mm = fractions.Fraction(int(mm * tk), tk)
		if float(mm) == float(ma) or float(mm) == float(mi):
			return mm
		if f(mm):
			mi = mm
		else:
			ma = mm
	if f(mm):
		return mm + eps
	return mm

def main():
	rr = []

	def f(w, h):
		a = [S() for _ in range(h)]
		si = sj = -1
		for i in range(1, h - 1):
			for j in range(1, w - 1):
				if a[i][j] == 's':
					si = i
					sj = j
					break

		def search(sc):
			d = collections.defaultdict(lambda : inf)
			q = []
			for i in range(1, h - 1):
				for j in range(1, w - 1):
					if a[i][j] == sc:
						d[i, j] = 0
						heapq.heappush(q, (0, (i, j)))
			v = collections.defaultdict(bool)
			while len(q):
				(k, u) = heapq.heappop(q)
				if v[u]:
					continue
				v[u] = True
				for (di, dj) in dd:
					ni = u[0] + di
					nj = u[1] + dj
					if not a[ni][nj] in '.s':
						continue
					uv = (ni, nj)
					if v[uv]:
						continue
					vd = k + 1
					if d[uv] > vd:
						d[uv] = vd
						heapq.heappush(q, (vd, uv))
			return d
		gd = search('g')
		wd = search('*')
		cgs = []
		cws = []
		for i in range(1, h - 1):
			for j in range(1, w - 1):
				if not a[i][j] in '.s':
					continue
				if gd[i, j] >= inf:
					cgs.append((i, j))
				else:
					cws.append((i, j))
		cc = len(cgs) + len(cws)
		cgc = len(cgs)
		cgw = sum([wd[i, j] for (i, j) in cgs])
		sgw = [(inf, 0, 0)]
		for (i, j) in cws:
			gt = gd[i, j]
			wt = wd[i, j]
			sgw.append((gt - wt, wt, gt))
		sgw.sort()
		ls = len(sgw) - 1

		def ff(t):
			s = cgw
			si = bisect.bisect_left(sgw, (t, 0, 0))
			tc = cgc
			s2 = cgw
			tc2 = tc + ls - si
			for i in range(si):
				s2 += sgw[i][2]
			for i in range(si, ls):
				s2 += sgw[i][1]
			av = (s2 + t * tc2) / cc
			return t < av
		k = bs(ff, 0, 10 ** 10)
		gt = gd[si, sj]
		wt = wd[si, sj]
		r = gt
		if wt + k < gt:
			r = wt + k
		return '{:0.10f}'.format(float(r))
	while 1:
		(n, m) = LI()
		if n == 0:
			break
		rr.append(f(n, m))
		break
	return '\n'.join(map(str, rr))
print(main())


from collections import deque
(w, h) = map(int, input().split())
mp = [input() for _ in range(h)]
springs = []
tile_cnt = 0
for y in range(h):
	for x in range(w):
		if mp[y][x] == '*':
			springs.append((x, y))
		if mp[y][x] == 'g':
			(gx, gy) = (x, y)
		if mp[y][x] == 's':
			(sx, sy) = (x, y)
			tile_cnt += 1
		if mp[y][x] == '.':
			tile_cnt += 1
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
INF = 10 ** 10
g_dist = [[INF] * w for _ in range(h)]
que = deque()
que.append((0, gx, gy))
g_dist[gy][gx] = 0
while que:
	(score, x, y) = que.popleft()
	for (dx, dy) in vec:
		(nx, ny) = (x + dx, y + dy)
		if mp[ny][nx] in ('.', 's'):
			if g_dist[ny][nx] == INF:
				g_dist[ny][nx] = score + 1
				que.append((score + 1, nx, ny))
s_dist = [[INF] * w for _ in range(h)]
que = deque()
for (x, y) in springs:
	s_dist[y][x] = 0
	que.append((0, x, y))
while que:
	(score, x, y) = que.popleft()
	for (dx, dy) in vec:
		(nx, ny) = (x + dx, y + dy)
		if mp[ny][nx] in ('.', 's'):
			if s_dist[ny][nx] == INF:
				s_dist[ny][nx] = score + 1
				que.append((score + 1, nx, ny))
sorted_tiles = sorted([(g_dist[y][x] - s_dist[y][x] if g_dist[y][x] != INF else INF, x, y) for y in range(h) for x in range(w) if mp[y][x] in ('.', 's')])
acc_g = 0
acc_s = 0
acc_t = 0
acc_g_dic = {}
acc_s_dic = {}
acc_t_dic = {}
keys = set()
for (key, x, y) in sorted_tiles:
	acc_g += g_dist[y][x]
	acc_s += s_dist[y][x]
	acc_t += 1
	acc_g_dic[key] = acc_g
	acc_s_dic[key] = acc_s
	acc_t_dic[key] = acc_t
	keys.add(key)
keys = sorted(list(keys))
length = len(keys)
for i in range(length - 1):
	key = keys[i]
	next_key = keys[i + 1]
	E = (acc_g_dic[key] + acc_s - acc_s_dic[key]) / acc_t_dic[key]
	if key <= E < next_key:
		print(min(g_dist[sy][sx], s_dist[sy][sx] + E))
		break
else:
	print(g_dist[sy][sx])