Problem: One day as Petya and his friend Vasya were having one of their numerous trips, they decided to visit a museum castle. The museum has a specific shape: it consists of n rooms connected with m corridors so that one can access any room from any other one.

After the two friends had a little walk around the museum, they decided to split and watch the pieces of art each of them found interesting. They agreed to meet in one of the rooms at six p.m. However, they forgot one quite essential thing: they didn't specify the place to meet and when the time came, they started to rush about the museum looking for each other (they couldn't call each other as roaming made a call's cost skyrocket).

Yet, even despite the whole rush, they couldn't get enough of the pieces of art, that's why each of them has the following strategy: each minute he make a decision where to go — with probability pi he doesn't move to any other place during this minute (i.e. he stays in the room). With probability 1 - pi he equiprobably choose one of the adjacent rooms and went there along the corridor. Here i is the ordinal number of the current room. Building was expensive in ancient times, that's why each corridor connected two different rooms, and any two rooms had no more than one corridor between them. 

The boys act simultaneously. As the corridors are dark, it is impossible to meet there; however, one can walk along the corridors in both directions (besides, the two boys can be going through the same corridor simultaneously without meeting). The boys act like that until they meet each other. More formally, the two friends meet when at some moment of time both of them decided to appear in the same room.

For each room find the probability that the boys will meet there considering that at 6 p.m. they are positioned in rooms a and b correspondingly.

Input

The first line contains four integers: n (1 ≤ n ≤ 22), representing the numbers of rooms; m <image>, representing the number of corridors; a, b (1 ≤ a, b ≤ n), representing the numbers of Petya's and Vasya's starting rooms correspondingly.

Next m lines contain pairs of numbers — the numbers of rooms connected by a corridor. Next n lines contain probabilities pi (0.01 ≤ pi ≤ 0.99) with the accuracy of up to four digits after the decimal point — the probability to stay in room i.

It is guaranteed that every room can be reached from every other room by corridors.

Output

In the only line print n space-separated numbers, the i-th number should represent the probability that the friends meet in the i-th room with absolute or relative error of no more than 10 - 6.

Examples

Input

2 1 1 2
1 2
0.5
0.5


Output

0.5000000000 0.5000000000 

Input

4 4 1 2
1 2
2 3
3 4
4 1
0.5
0.5
0.5
0.5


Output

0.3333333333 0.3333333333 0.1666666667 0.1666666667 

Note

In the first sample the museum is symmetric. That means the probabilities to meet in rooms 1 and 2 are equal. And their sum equals to one. So, each probability equals 0.5.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
std::istream &operator>>(std::istream &i, pair<T, U> &p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T>
std::istream &operator>>(std::istream &i, vector<T> &t) {
  for (auto &v : t) {
    i >> v;
  }
  return i;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &o, const pair<T, U> &p) {
  o << p.first << ' ' << p.second;
  return o;
}
template <typename T>
std::ostream &operator<<(std::ostream &o, const vector<T> &t) {
  if (t.empty()) o << '\n';
  for (size_t i = 0; i < t.size(); ++i) {
    o << t[i] << " \n"[i == t.size() - 1];
  }
  return o;
}
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
bool in(T a, T b, T c) {
  return a <= b && b < c;
}
unsigned int logceil(int first) {
  return 8 * sizeof(int) - __builtin_clz(first);
}
namespace std {
template <typename T, typename U>
struct hash<pair<T, U>> {
  hash<T> t;
  hash<U> u;
  size_t operator()(const pair<T, U> &p) const {
    return t(p.first) ^ (u(p.second) << 7);
  }
};
}  // namespace std
template <typename T, typename F>
T bsh(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      l = m + 1;
      r = m;
    } else {
      h = m - 1;
    }
  }
  return r;
}
template <typename F>
double bshd(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      l = m;
    } else {
      h = m;
    }
  }
  return (l + h) / 2;
}
template <typename T, typename F>
T bsl(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      h = m - 1;
      r = m;
    } else {
      l = m + 1;
    }
  }
  return r;
}
template <typename F>
double bsld(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      h = m;
    } else {
      l = m;
    }
  }
  return (l + h) / 2;
}
template <typename T>
T gcd(T a, T b) {
  if (a < b) swap(a, b);
  return b ? gcd(b, a % b) : a;
}
template <typename T>
class vector2 : public vector<vector<T>> {
 public:
  vector2() {}
  vector2(size_t a, size_t b, T t = T())
      : vector<vector<T>>(a, vector<T>(b, t)) {}
};
template <typename T>
class vector3 : public vector<vector2<T>> {
 public:
  vector3() {}
  vector3(size_t a, size_t b, size_t c, T t = T())
      : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}
};
template <typename T>
class vector4 : public vector<vector3<T>> {
 public:
  vector4() {}
  vector4(size_t a, size_t b, size_t c, size_t d, T t = T())
      : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}
};
template <typename T>
class vector5 : public vector<vector4<T>> {
 public:
  vector5() {}
  vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())
      : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}
};
template <typename T>
class Matrix {
 public:
  Matrix(size_t R, size_t C, T t = T(0))
      : R(R), C(C), A(R, vector<T>(C, t)), def(t) {}
  Matrix(const vector<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a[0].size()), A(a), def(t) {}
  Matrix(const initializer_list<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a.begin()->size()), A(a), def(t) {}
  size_t rows() const { return R; }
  size_t columns() const { return C; }
  bool isSquare() const { return R * C; }
  bool isIdentity() const {
    for (int i = 0; i < min(R, C); ++i) {
      for (int j = 0; j < min(R, C); ++j) {
        if (i == j && A[i][j] != 1) return false;
        if (i != j && A[i][j] != 0) return false;
      }
    }
    return true;
  }
  void addColumnsRight(size_t add, T t = T()) {
    for (int i = 0; i < R; ++i) {
      A[i].resize(C + add);
      for (size_t j = C; j < C + add; ++j) A[i][j] = t;
    }
    C += add;
  }
  void removeColumnsLeft(size_t rem) {
    for (size_t i = 0; i < R; ++i)
      A[i].erase(A[i].begin(),
                 rem > A[i].size() ? A[i].end() : A[i].begin() + rem);
  }
  T determinant() const {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> tmp(*this);
    T ans = tmp.toReducedRowEchelon();
    if (tmp.isIdentity())
      return ans;
    else
      return 0;
  }
  vector<T> solveFor(const vector<T> &b) {
    if (!isSquare()) {
      throw std::runtime_error("Cannot solve a rectangular matrix");
    }
    if (b.size() != R)
      throw new std::runtime_error(
          "Unable to solve linear equation, dimensions do not match");
    Matrix<T> tmp(*this);
    for (int i = 0; i < R; ++i) tmp.A[i].push_back(b[i]);
    ++tmp.C;
    tmp.toReducedRowEchelon();
    if (!tmp.isIdentity())
      throw std::runtime_error("Cannot solve a singular matrix");
    vector<T> Ans(R);
    for (int j = 0; j < R; ++j) Ans[j] = tmp.A[j].back();
    return Ans;
  }
  Matrix<T> power(unsigned long long N) {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> ans(R, R, 0), pow = *this;
    for (unsigned int r = 0; r < R; ++r) ans[r][r] = 1;
    while (N) {
      if (N & 1) ans = ans * pow;
      N >>= 1;
      pow = pow * pow;
    }
    return ans;
  }
  Matrix<T> &operator+=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot add matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot add matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] += m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> &operator-=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot substract matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot substract matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] -= m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> operator*(const Matrix<T> &m) const {
    if (C != m.R)
      throw std::runtime_error("Matrices incompatible for multiplication");
    Matrix<T> Ans(R, m.C, T(0));
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < m.C; ++j) {
        for (int k = 0; k < C; ++k) {
          Ans[i][j] += A[i][k] * m.A[k][j];
        }
      }
    }
    return Ans;
  }
  vector<T> operator*(const vector<T> &m) const {
    if (C != m.size())
      throw std::runtime_error(
          "Matric and vector incompatible for multiplication");
    vector<T> ans(R, def);
    for (unsigned int r = 0; r < R; ++r) {
      for (unsigned int c = 0; c < C; ++c) {
        ans[r] += m[c] * (*this)[r][c];
      }
    }
    return ans;
  }
  class Row {
   public:
    Row(Matrix<T> *M, size_t row) : M(M), row(row) {}
    T &operator[](size_t col) {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }
    const T &operator[](size_t col) const {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }

   private:
    Matrix<T> *M;
    size_t row;
  };
  Row operator[](size_t row) {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(this, row);
  }
  const Row operator[](size_t row) const {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(const_cast<Matrix<T> *>(this), row);
  }
  Matrix<T> transposed() const {
    Matrix<T> M(*this);
    M.transpose();
    return M;
  }
  Matrix<T> inverted() const {
    if (R != C) throw std::runtime_error("Matrix not square");
    Matrix<T> M(*this);
    M.invert();
    return M;
  }
  Matrix<T> &transpose() {
    A.resize(max(R, C));
    for (size_t i = 0; i < C; ++i) A[i].resize(max(R, C));
    for (size_t i = 0; i < R; ++i) {
      for (size_t j = i + 1; j < C; ++j) swap(A[i][j], A[j][i]);
    }
    for (size_t i = 0; i < C; ++i) A[i].resize(R);
    A.resize(C);
    return *this;
  }
  Matrix<T> &invert() {
    addColumnsRight(C, def);
    for (size_t i = 0; i < R; ++i) A[i][R + i] = 1;
    toReducedRowEchelon();
    if (!isIdentity()) throw std::runtime_error("Matrix not invertible");
    removeColumnsLeft(C / 2);
    return *this;
  }
  T toReducedRowEchelon() {
    size_t pivot = 0;
    T factor = 1;
    for (size_t i = 0; i < C && pivot < R; ++i) {
      pair<T, size_t> Q = {abs(A[pivot][i]), pivot};
      for (size_t j = pivot + 1; j < R; ++j) Q = max(Q, {abs(A[j][i]), j});
      if (Q.first == 0) continue;
      if (Q.second != i) swap(A[Q.second], A[pivot]);
      for (size_t j = i + 1; j < C; ++j) A[pivot][j] /= A[pivot][i];
      factor /= A[pivot][i];
      A[pivot][i] = 1;
      for (size_t j = 0; j < R; ++j) {
        if (j != pivot) {
          for (size_t k = i + 1; k < C; ++k) A[j][k] -= A[pivot][k] * A[j][i];
          A[j][i] = 0;
        }
      }
      ++pivot;
    }
    return factor;
  }
  size_t R, C;
  vector<vector<T>> A;
  T def;
};
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &m) {
  for (size_t r = 0; r < m.rows(); ++r)
    for (size_t c = 0; c < m.columns(); ++c)
      os << m[r][c] << " \n"[c == m.columns() - 1];
  return os;
}
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);
using random_int = std::uniform_int_distribution<int>;
using random_ll = std::uniform_int_distribution<long long>;
struct TimeLimit {
  TimeLimit(double seconds) : s(seconds - 0.1), last(clock()), mx(0) {}
  operator bool() const {
    clock_t cur = clock();
    mx = max(mx, cur - last);
    last = cur;
    return clock() < s * CLOCKS_PER_SEC - 1.5 * mx;
  }
  double s;
  mutable clock_t last, mx;
};
class Museum {
 public:
  void solve(istream &cin, ostream &cout) {
    int N, M, A, B;
    cin >> N >> M >> A >> B;
    --A;
    --B;
    if (N == 1) {
      cout << "1.000000000\n";
      return;
    }
    vector<vector<int>> E(N);
    for (int i = 0; i < M; ++i) {
      int u, v;
      cin >> u >> v;
      --u;
      --v;
      E[u].push_back(v);
      E[v].push_back(u);
    }
    vector<double> P(N);
    cin >> P;
    vector2<double> W(N, N, 0);
    for (int i = 0; i < N; ++i) {
      for (int j : E[i]) {
        W[j][i] = (1 - P[i]) / E[i].size();
      }
      W[i][i] = P[i];
    }
    Matrix<double> F(N * N, N * N + N, 0);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (i == j)
          F[i * N + j][i * N + j] = 1;
        else {
          for (int k = 0; k < N; ++k) {
            for (int l = 0; l < N; ++l) {
              F[i * N + j][k * N + l] += W[k][i] * W[l][j];
            }
          }
          F[i * N + j][i * N + j] -= 1;
        }
      }
      F[i * (N + 1)][N * N + i] = 1;
    }
    F.toReducedRowEchelon();
    vector<double> Ans(N);
    for (int i = 0; i < N; ++i) {
      Ans[i] = F[A * N + B][N * N + i];
    }
    cout << fixed << setprecision(10) << Ans;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  Museum solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}