Problem: 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.

<image>

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

Solution (in CPP):

Solution:
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = int; using P = pair<ll, ll>;
const ll linf = 2e9; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

struct Node {
  ll x, y, c;
};
bool operator>(const Node& n1, const Node& n2) {
  return n1.c > n2.c;
}

ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};

ll dist[1000][1000];
string m[1000];
ll h, w, A, B;

bool inRange(ll x, ll y) {
  return 0 <= x && x < w && 0 <= y && y < h;
}

template <class Monoid>
class SegmentTree {
  using T = typename Monoid::type;
  const int size_, n;
  std::vector<T> data;
  int expand(int m) const { return m <= 1 ? 1 : expand((m + 1) / 2) * 2; }
public:
  SegmentTree() : SegmentTree(0) {}
  SegmentTree(const std::vector<T> &vec) :
    size_(vec.size()), n(expand(size_)), data(n * 2, Monoid::id()) {
    std::copy(begin(vec), end(vec), begin(data) + n);
    for (int i = n - 1; i >= 0; --i) {
      data[i] = Monoid::op(data[i * 2 + 0], data[i * 2 + 1]);
    }
  }
  SegmentTree(const int count, const T &value = Monoid::id()) :
    SegmentTree(std::vector<T>(count, value)) {}
  int size() const { return size_; }
  void update(int pos, const T &value) {
    assert (0 <= pos && pos < size_); // assertion
    data[pos += n] = value;
    while (pos /= 2) {
      data[pos] = Monoid::op(data[pos * 2], data[pos * 2 + 1]);
    }
  }
  T find(int l, int r) const {
    assert (0 <= l && l <= r && r <= size_); // assertion
    l += n; r += n;
    T res1 = Monoid::id(), res2 = Monoid::id();
    while (l != r) {
      if (l % 2) res1 = Monoid::op(res1, data[l++]);
      if (r % 2) res2 = Monoid::op(data[--r], res2);
      l /= 2; r /= 2;
    }
    return Monoid::op(res1, res2);
  }
  using value_type = T;
  using update_type = T;
};

struct Min {
  using type = P;
  static type id() { return P(linf, linf); }
  static type op(const type &l, const type &r) { return min(l, r); }
};
struct Max {
  using type = ll;
  static type id() { return -linf; }
  static type op(const type &l, const type &r) { return max(l, r); }
};
struct Sum {
  using type = ll;
  static type id() { return 0; }
  static type op(const type &l, const type &r) { return l + r; }
};

#define ID(x, y) (y * w + x)

void solve() {
  cin >> h >> w >> A >> B;
  rep(y, h) cin >> m[y];
  ll sx, sy, gx, gy;
  rep(y, h) rep(x, w) {
    if (m[y][x] == 's') sx = x, sy = y;
    if (m[y][x] == 'g') gx = x, gy = y;
  }
  fill(dist[0], dist[1000], linf);
  dist[sy][sx] = 0;
  SegmentTree<Min> seg(w * h);
  seg.update(ID(sx, sy), P(0, ID(sx, sy)));
  while (true) {
    P p = seg.find(0, w*h);
    if (p.first == linf) break;
    ll id = p.second;
    ll x = id % w, y = id / w;
    ll c = dist[y][x];
    seg.update(ID(x, y), P(linf, -1));
    // 普通に移動
    rep(d, 4) {
      ll nx = x + dx[d];
      ll ny = y + dy[d];
      if (inRange(nx, ny) && m[ny][nx] != '#' && c + A <= dist[ny][nx]) {
        dist[ny][nx] = c + A;
        seg.update(ID(nx, ny), P(dist[ny][nx], ID(nx, ny)));
      }
    }
    // 能力を使って移動
    bool can = true;
    rep(dx, -1, 2) rep(dy, -1, 2) {
      ll nx = x + dx, ny = y + dy;
      if (inRange(nx, ny) && m[ny][nx] == '*') {
        can = false;
      }
    }
    if (can) {
      rep(dx, -1, 2) rep(dy, -1, 2) {
        ll nx = x + dx;
        ll ny = y + dy;
        ll nc = c + A * (abs(dx) + abs(dy)) + B;
        if (inRange(nx, ny) && nc <= dist[ny][nx]) {
          dist[ny][nx] = nc;
          seg.update(ID(nx, ny), P(dist[ny][nx], ID(nx, ny)));
        }
      }
    }
  }
  if (dist[gy][gx] == linf) {
    cout << "INF" << endl;
  }
  else {
    cout << dist[gy][gx] << endl;
  }
}