Problem: In the country there are n cities and m bidirectional roads between them. Each city has an army. Army of the i-th city consists of ai soldiers. Now soldiers roam. After roaming each soldier has to either stay in his city or to go to the one of neighboring cities by at moving along at most one road.

Check if is it possible that after roaming there will be exactly bi soldiers in the i-th city.

Input

First line of input consists of two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 200).

Next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 100).

Next line contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 100).

Then m lines follow, each of them consists of two integers p and q (1 ≤ p, q ≤ n, p ≠ q) denoting that there is an undirected road between cities p and q. 

It is guaranteed that there is at most one road between each pair of cities.

Output

If the conditions can not be met output single word "NO".

Otherwise output word "YES" and then n lines, each of them consisting of n integers. Number in the i-th line in the j-th column should denote how many soldiers should road from city i to city j (if i ≠ j) or how many soldiers should stay in city i (if i = j).

If there are several possible answers you may output any of them.

Examples

Input

4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2


Output

YES
1 0 0 0 
2 0 0 0 
0 5 1 0 
0 0 2 1 


Input

2 0
1 2
2 1


Output

NO

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;


 
public class A {
	public static class dinic{
		// Refer to https://www.youtube.com/watch?v=_SdF4KK_dyM
		
		List<Edge>[] g;
		long ans = 0;
		int[] l; // level graph
		int[] next; // Prunes dead ends. If index 0 is a dead end, next[i] = 1, because we skip 0, and so on. 
		int S = 0; // Let S be maxN.
		long INF = Long.MAX_VALUE/2;
		
		public dinic(int s) { // s is the preicse number of nodes.
			S = s+10; // Let S be the index of the source, and T =S+1 be the index of the of the sink.
			g = new List[S+2];
			l = new int[S+2];
			next = new int[S+2];
			for (int i =0 ; i < g.length; i++) {
				g[i] = new ArrayList<Edge>();
			}
			
		}
		

		long solve() {
			long maxflow = 0;
			while(bfs()) {
				Arrays.fill(next, 0);
				for (long f = dfs(S, INF); f != 0; f = dfs(S, INF)) {
					maxflow += f;
				}
			}
			return maxflow; 
		}
		
		boolean bfs() {
			Deque<Integer> q = new ArrayDeque<Integer>();
			q.add(S);
			Arrays.fill(l, -1);
			l[S] = 0;
			while (!q.isEmpty()) {
				int h = q.poll();
				for (Edge e: g[h]) {
					if (e.remCap() > 0 && l[e.i] == -1) {
						l[e.i] =  l[h]+1;
						q.add(e.i);
					}
				}
			}
			return l[S+1] != -1; // If its's -1, then we failed. 
		}
		
		class Edge{
			
			int i, flip; // Flip is the opposite edge. Accessible via g[e.i][e.flip].
			long cap, flow; // max and cur
			public Edge(int w, long x, long y, int res) {
				i=w;
				cap=x;
				flow=y;
				flip = res;
			}
			public long remCap() {
				// Remaining capcacity. cap - flow.
				return cap-flow;
			}
			public void augment(long flo) {
				flow += flo;
				g[i].get(flip).flow-=flo;
			}
		}
		
		
		void addEdge(int a, int b, long cap) {
			g[a].add(new Edge(b, cap, 0, g[b].size()));
			g[b].add(new Edge(a, 0, 0, g[a].size()-1));
		}
		
		long dfs(int i, long flow) {
			if (i == S+1 || flow == 0) return flow;
			
			for(;next[i] < g[i].size(); next[i]++) {
				Edge e= g[i].get(next[i]);
				if (e.remCap() > 0 && l[i] + 1== l[e.i]) {
					
					long bottleNeck = dfs(e.i, Long.min(flow, e.remCap()));
					if (bottleNeck > 0) {
						// Augmenting increases current flow and decreases residual flow.
						e.augment(bottleNeck);
						return bottleNeck;
					}
				}
			}
			return 0;
		}
		//Explanation of how the DFS works
		// Passing bottleneck through will either reach the sink (in which we return the bottleneck) or 0, which means we can't anymore.
		// Then, because we called bottleneck first, we can use that new value and recursively assign backwards.
		// Next[i]++ will only activate if we did not return a bottleneck, in which case we know that this is a dead end.
		
	}
	
	public static Reader sc = new Reader();
	//public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader("input.in"));

		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		long sa = 0;
		long sb = 0;
		dinic d = new dinic(n*2);

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt(); sa += a[i];
			d.addEdge(d.S, i, a[i]);
		}
		for (int i = 0; i < n; i++) {
			b[i] = sc.nextInt(); sb += b[i];
			d.addEdge(i+n, d.S+1, b[i]);
		}

		for (int i = 0; i < m; i++) {
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			
			d.addEdge(x, y+n, d.INF);
			d.addEdge(y, x+n, d.INF);
		}
		for (int i = 0; i  <n; i++) {
			d.addEdge(i,i+n, d.INF);
		}
		
		long res = d.solve();
		if (res == sa && res == sb) {
			out.println("YES");
			long[][] num = new long[n][n];
			for (int i = 0; i < n;  i++) {
				for (int j = 0; j < d.g[i].size(); j++) {
					if (d.g[i].get(j).i >= n && d.g[i].get(j).i < 2*n) {
						num[i][d.g[i].get(j).i-n]=d.g[i].get(j).flow;
					}
				}
				
			}
			for (long[] nu: num) {
				for (long x: nu) {
					out.print(x + " ");
				}
				out.println();
			}
		}
		else out.println("NO");

		out.close();
	}

	static long ceil(long a, long b) {
		return (a + b - 1) / b;
	}

	static long powMod(long base, long exp, long mod) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base % mod;
		long R = powMod(base, exp / 2, mod) % mod;
		R *= R;
		R %= mod;
		if ((exp & 1) == 1) {
			return base * R % mod;
		} else
			return R % mod;
	}

	static long pow(long base, long exp) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base;
		long R = pow(base, exp / 2);
		if ((exp & 1) == 1) {
			return R * R * base;
		} else
			return R * R;
	}

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					break;
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, Integer.max(cnt - 1, 0));
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
}