Don't Burn Kotatsu Turtle

Problem

Kotatsu turtle is a turtle with a kotatsu shell.

As soon as Kotatsu was pokita (getting up), he was trapped in a stage divided into grid-like sections. There is only one exit on this stage. The parcel is either a road, a fence or a bomb, and the kotatsu can move up, down, left and right to enter the parcel of the road or bomb. It cannot be moved diagonally. In addition, the fence section cannot be passed. The road section extends infinitely outside the stage, but it cannot be passed because there is a crocodile, the natural enemy of the turtle.

Kotatsu wants to go home (sleep) quickly, so I decided to head to the exit of this stage.

The kotatsu turtle, which can freely manipulate the infrared rays of the kotatsu, has the ability to turn eight sections around it into a road at the same time. However, if the 8 sections and one of the sections where you are located are bomb sections, the kotatsu will burn up when you explode, and you will not even be able to use the famous SNS "Kametta", so you will activate the ability. I can't do that.

An example is illustrated. The section where the illustration is not placed and the section where the kotatsu is placed are the sections of the road. The eight compartments around the kotatsu are the orange compartments. In the figure on the left, the 8 compartments around the kotatsu and the compartment where you are are not included in the bomb compartment, so you can activate the ability. However, in the figure on the right, the ability cannot be activated because the bomb compartment is included in either the surrounding 8 compartments or the compartment where you are.

The cost to move is $A$ for each parcel move, and the cost to activate the ability is $B$ each time. Please note that it is not the cost per wall turned into a road. The starting point and the exit of the stage are roads. Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Constraints

The input satisfies the following conditions.

• $1 \ le H, W, A, B \ le 1000$
• $3 \ le H + W$
• $c_ {i, j} \ in$ {'s','g','.','#','*'} *'s' and'g' appear once each

Input

The input is given in the following format.

$H$ $W$ $A$ $B$ $c_ {1,1} \ cdots c_ {1, W}$ $\ vdots$ $c_ {H, 1} \ cdots c_ {H, W}$

The input consists of $H + 1$ lines. On the $1$ line, there are an integer $H$ that represents the vertical length, an integer $W$ that represents the left and right length, an integer $A$ that represents the cost to move, and an integer $B$ that represents the cost to activate the ability. Each is given with a blank delimiter. The $H$ line from the $2$ line is given the state $c_ {i, j}$ in each section of the stage where the kotatsu is confined. $c_ {i, j}$ consists of one of's','g','.','#','', Each, and the partition $(i, j)$ is in the following state. Represents that. 's': Indicates that the section is the starting point. 'g': Indicates that the parcel is the exit of the stage. '.': Indicates that the section is a road. '#': Indicates that the section is a fence. '': Indicates that the parcel is a bomb.

Output

Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Examples

Input

4 4 1 1 g#.. #... .*.. ...s

Output

7

Input

4 4 1 1 g#.. ... .*.. ...s

Output

7

Input

4 4 1 1 g#.. *.. .... ...s

Output

INF

Input

2 4 1 1 g s###

Output

6

Input

3 3 1 10 g.. . s..

Output

6

Input

3 3 10 1 g.. . s..

Output

21

inputFormat

outputFormat

Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Constraints

The input satisfies the following conditions.

• $1 \ le H, W, A, B \ le 1000$
• $3 \ le H + W$
• $c_ {i, j} \ in$ {'s','g','.','#','*'} *'s' and'g' appear once each

Input

The input is given in the following format.

$H$ $W$ $A$ $B$ $c_ {1,1} \ cdots c_ {1, W}$ $\ vdots$ $c_ {H, 1} \ cdots c_ {H, W}$

The input consists of $H + 1$ lines. On the $1$ line, there are an integer $H$ that represents the vertical length, an integer $W$ that represents the left and right length, an integer $A$ that represents the cost to move, and an integer $B$ that represents the cost to activate the ability. Each is given with a blank delimiter. The $H$ line from the $2$ line is given the state $c_ {i, j}$ in each section of the stage where the kotatsu is confined. $c_ {i, j}$ consists of one of's','g','.','#','', Each, and the partition $(i, j)$ is in the following state. Represents that. 's': Indicates that the section is the starting point. 'g': Indicates that the parcel is the exit of the stage. '.': Indicates that the section is a road. '#': Indicates that the section is a fence. '': Indicates that the parcel is a bomb.

Output

Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Examples

Input

4 4 1 1 g#.. #... .*.. ...s

Output

7

Input

4 4 1 1 g#.. ... .*.. ...s

Output

7

Input

4 4 1 1 g#.. *.. .... ...s

Output

INF

Input

2 4 1 1 g s###

Output

6

Input

3 3 1 10 g.. . s..

Output

6

Input

3 3 10 1 g.. . s..

Output

21

样例

2 4 1 1
g
s###

6