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 JAVA):

Solution:
import static java.util.Arrays.deepToString;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.*;


public class D {

	static void solve() throws Exception {
		int n = nextInt();
		int m = nextInt();
		int a = nextInt() - 1;
		int b = nextInt() - 1;
		boolean[][] g = new boolean[n][n];
		int[] deg = new int[n];
		for (int i = 0; i < n; i++) {
			g[i][i] = true;
		}
		for (int i = 0; i < m; i++) {
			int u = nextInt() - 1;
			int v = nextInt() - 1;
			g[u][v] = true;
			g[v][u] = true;
			deg[u]++;
			deg[v]++;
		}
		double[] p = new double[n];
		for (int i = 0; i < n; i++) {
			p[i] = nextDouble();
		}
		double [][] pr = new double[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j == i) {
					pr[i][j] = p[i];
				} else {
					if (g[i][j]) {
						pr[i][j] = (1 - p[i]) / deg[i];
					}
				}
			}
		}

		int st = n * n;

		double[][] A = new double[st][st];
		double[][] YL = new double[n][st];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int state = i * n + j;
				A[state][state] = 1;
				if (i == j) {
					YL[i][state] += 1;
					continue;
				}
				for (int ni = 0; ni < n; ni++) {
					for (int nj = 0; nj < n; nj++) {
						int nstate = ni * n + nj;
						if (g[i][ni] && g[j][nj]) {
							if (ni != nj) {
								A[state][nstate] -= pr[i][ni] * pr[j][nj];
							} else {
								YL[nj][state] += pr[i][ni] * pr[j][nj];
							}
						}
					}
				}
			}
		}

		M matrix = new M(st);
		matrix.a = A;
		M invMatrix = matrix.inverse();

		double[] ans = new double[n];
		for (int last = 0; last < n; last++) {
			double[] prob = invMatrix.apply(YL[last]);
			ans[last] = prob[a * n + b];
			out.print(ans[last] + " ");
		}
	}

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();

			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;
	static long launchTimer;

	static void debug(Object... o) {
		System.err.println(deepToString(o));
	}

	static void setTime() {
		launchTimer = System.currentTimeMillis();
	}

	static void printTime() {
		System.err.println(System.currentTimeMillis() - launchTimer);
	}

	static void printMemory() {
		System.err.println((Runtime.getRuntime().totalMemory() - Runtime
				.getRuntime().freeMemory()) / 1000 + "kb");
	}

	static boolean hasMoreTokens() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return false;
			}
			tok = new StringTokenizer(line);
		}
		return true;
	}

	static String next() throws IOException {
		return hasMoreTokens() ? tok.nextToken() : null;
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static BigInteger nextBig() throws IOException {
		return new BigInteger(next());
	}
}

class M {
	int n;
	double[][] a;

	M(int n) {
		this.n = n;
		a = new double[n][n];
	}

	static M I(int n) {
		M ret = new M(n);
		for (int i = 0; i < n; i++)
			ret.a[i][i] = 1;
		return ret;
	}

	double[] apply(double[] v) {
		assert (v.length == n);
		double[] ret = new double[n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ret[i] += a[i][j] * v[j];
			}
		}
		return ret;
	}

	final double eps = 1e-8;

	void rowSwap(int i, int j) {
		double[] tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	void multRow(int i, double c) {
		for (int j = 0; j < n; j++)
			a[i][j] *= c;
	}

	// a_i -= a_j * c
	void subRow(int i, int j, double c) {
		for (int t = 0; t < n; t++)
			a[i][t] -= a[j][t] * c;
	}

	M inverse() {
		M m = new M(n).add(this), ret = I(n);
		for (int i = 0; i < n; i++) {
			int br = i;
			for (int j = i + 1; j < n; j++) {
				if (abs(m.a[j][i]) > abs(m.a[br][i]))
					br = j;
			}
			if (abs(m.a[br][i]) < eps)
				return null; // no inverse
			m.rowSwap(i, br);
			ret.rowSwap(i, br);
			double c = 1 / m.a[i][i];
			m.multRow(i, c);
			ret.multRow(i, c);
			for (int j = 0; j < n; j++)
				if (j != i) {
					c = m.a[j][i];
					m.subRow(j, i, c);
					ret.subRow(j, i, c);
				}
		}
		return ret;
	}

	M add(M r) {
		M ret = new M(n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				ret.a[i][j] = a[i][j] + r.a[i][j];
		return ret;
	}

	public String toString() {
		String ret = "";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				ret += String.format("%5.3f ", a[i][j]);
			ret += "\n";
		}
		return ret;
	}
}