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 B {

    public static void main(String[] args) {
        FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        Task solver = new Task();
        int t = 1;
        for(int tt = 1; tt <= t; tt++) solver.solve(tt, scan, out);
        out.close();
    }

    static class Task {
    
        public void solve(int testNumber, FastReader scan, PrintWriter out) {
            int n = scan.nextInt(), m = scan.nextInt();
            Dinic graph = new Dinic(n + n);
            int[] a = new int[n];
            int need = 0;
            for(int i = 0; i < n; i++) {
                a[i] = scan.nextInt();
                graph.add( 2* n, i, a[i], 0);
                graph.add(i, n + i, a[i], 0);
            }
            for(int i = 0; i < n; i++) {
                int b = scan.nextInt();
                graph.add(n + i, 2 * n + 1, b, 0);
                need += b;
            }
            for(int i = 0; i < m; i++) {
                int u = scan.nextInt() - 1, v = scan.nextInt() - 1;
                graph.add(u, n + v, a[u], 0);
                graph.add(v, n + u, a[v], 0);

            }
            boolean bad = graph.flow() != need;
            int[][] res = new int[n][n];
            for(Dinic.Edge e : graph.edges) {
                if(e.v1 == 2 * n) {
                    bad |= e.flow != a[e.v2];
                }
                else if(e.v1 < 2 * n && e.v2 < 2 * n) {
                    res[e.v1][e.v2 - n] = e.flow;
                }
            }
            if(!bad) {
                out.println("YES");
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < n; j++) {
                        out.printf("%d ", res[i][j]);
                    }
                    out.println();
                }
            }
            else {
                out.println("NO");
            }
        }

        static class Dinic {
            static class Edge {  int v1, v2, cap, flow; Edge rev;
                Edge(int V1, int V2, int Cap, int Flow) { v1 = V1; v2 = V2; cap = Cap; flow = Flow; }
            }

            ArrayDeque<Integer> q;  ArrayList<Edge>[] adj;
            ArrayList<Edge> edges;
            int n, s, t, mS, mT, oo = (int)1E9;
            boolean[] blocked;  int[] dist;
            public Dinic (int N) {
                n = N; s = n++; t = n++; mS = n++; mT = n++; blocked = new boolean[n];
                dist = new int[n];  q = new ArrayDeque<Integer>();
                adj = new ArrayList[n];  for(int i = 0; i < n; ++i)  adj[i] = new ArrayList<Edge>();
                edges = new ArrayList<>();
            }
            // Specifying flow can represent minimum flow for circulation.
            Edge add(int v1, int v2, int cap, int flow) {
                Edge e = new Edge(v1, v2, cap, flow);  Edge rev = new Edge(v2, v1, 0, 0);
                edges.add(e);
                adj[v1].add(rev.rev = e);  adj[v2].add(e.rev = rev);
                return e;
            }

            //#
            // Only needed if you need remove function
            void remove(int v1, int v2) {
                Edge e;
                for(int i = 0; i < adj[v1].size(); i++) {
                    e = adj[v1].get(i);
                    if(e.v2 == v2 && e.cap != 0)  adj[v1].remove(i--);
                }

                for(int i = 0; i < adj[v2].size(); i++) {
                    e = adj[v2].get(i);
                    if(e.v2 == v1 && e.cap == 0)  adj[v2].remove(i--);
                }
            }
            //$

            boolean bfs() {
                q.clear();  Arrays.fill(dist, -1);  dist[t] = 0;  q.add(t);

                while(!q.isEmpty()) {
                    int node = q.poll();
                    if(node == s)   return true;
                    for(Edge e : adj[node]) {
                        if(e.rev.cap > e.rev.flow && dist[e.v2] == -1) {
                            dist[e.v2] = dist[node] + 1;  q.add(e.v2);
                        }
                    }
                }
                return dist[s] != -1;
            }

            int dfs(int pos, int min) {
                if(pos == t)  return min;
                int flow = 0;
                for(Edge e : adj[pos]) {
                    int cur = 0;
                    if(!blocked[e.v2] && dist[e.v2] == dist[pos]-1 && e.cap - e.flow > 0) {
                        cur = dfs(e.v2, Math.min(min-flow, e.cap - e.flow));
                        e.flow += cur;  e.rev.flow = -e.flow;  flow += cur;
                    }
                    if(flow == min)  return flow;
                }
                blocked[pos] = flow != min;
                return flow;
            }
            int flow() {
                clear();  int ret = 0;
                while(bfs()) {  Arrays.fill(blocked, false);  ret += dfs(s, oo);  }
                return ret;
            }
            void clear() {  for(ArrayList<Edge> edges : adj)  for(Edge e : edges)  e.flow = 0;  }
            // Convert the given graph into a graph to test for circulation
            boolean circulation() {
                int[] delta = new int[n];
                Dinic d = new Dinic(n);
                for(int node = 0; node < n; ++node) {
                    for(Edge e : adj[node]) {
                        if(e.cap > 0 && e.flow >= 0) {
                            d.add(e.v1, e.v2, e.cap-e.flow, 0);
                            delta[e.v1] -= e.flow;  delta[e.v2] += e.flow;
                        }
                    }
                }
                ArrayList<Edge> satEdges = new ArrayList<Edge>();
                for(int i = 0; i < n; ++i) {
                    if(delta[i] > 0)  satEdges.add(d.add(d.s, i, delta[i], 0));
                    else if(delta[i] < 0)  d.add(i, d.t, -delta[i], 0);
                }
                Edge tylerEdge = d.add(t,s,oo,0);
                int flow = d.flow();
                boolean isSat = true;
                for(Edge e : satEdges) isSat&=(e.cap==e.flow);
                return isSat;
            }

            int maxFlowWithMinCap() {
                Edge e = add(t,s,oo,0);
                int lo = 0, hi = oo;
                while(lo < hi) {
                    int mid = (lo+hi+1)/2;
                    e.flow = mid;
                    if(circulation()) lo = mid;
                    else hi = mid-1;
                }
                return lo;
            }
            int minFlowWithMinCap() {
                Edge e1 = add(mS, s, 1, 0);
                Edge e2 = add(t, mT, oo, 0);
                add(s, t, oo, 0);
                s = mS; t = mT;
                int lo = 0, hi = oo;
                while(lo < hi) {
                    int mid = (lo+hi)/2;
                    e1.cap = mid;
                    e2.flow = mid;
                    if(circulation()) hi = mid;
                    else lo = mid+1;
                }
                return lo;
            }
            /* Vertex cover on bipartite graph (L, R):
            Find nodes in S side of S/T min cut (bfs(); dist[i] == -1)
            L1 = L & S, L2 = L - S, R1 = R & S, R2 = R - S
            Let B be the set of vertices in R2 that have neighbors in L1
            C = L2 | R1 | B
            Maximum independent set is the complement nodes
            To get all nodes that can be in max independent set, get vertexCover()
            then swap source/sink and bfs on saturated edges, then get next vc()
            Nodes that DONT appear in BOTH can be part of max independent set*/
            ArrayList<Integer> vertexCover() {
                BitSet leftNodes = new BitSet();
                BitSet rightNodes = new BitSet();
                BitSet minCut = new BitSet();
                for(Edge e : adj[s])
                    if(e.v1 == s)
                        leftNodes.set(e.v2);
                for(Edge e : adj[t])
                    if(e.v1 == t)
                        rightNodes.set(e.v2);
                bfs();
                for(int i = 0; i < s; ++i)
                    if(dist[i] == -1)
                        minCut.set(i);

                BitSet l1 = new BitSet(); l1.or(leftNodes); l1.and(minCut);
                BitSet l2 = new BitSet(); l2.or(leftNodes); l2.andNot(minCut);
                BitSet r1 = new BitSet(); r1.or(rightNodes); r1.and(minCut);
                BitSet r2 = new BitSet(); r2.or(rightNodes); r2.andNot(minCut);

                BitSet b = new BitSet();
                for(int bit = r2.nextSetBit(0); bit >= 0; bit = r2.nextSetBit(bit+1)) {
                    for(Edge e : adj[bit]) {
                        if(e.v1 == bit && l1.get(e.v2)) {
                            b.set(bit);
                            break;
                        }
                    }
                }

                BitSet c = new BitSet(); c.or(l2); c.or(r1); c.or(b);
                ArrayList<Integer> ret = new ArrayList<Integer>();
                for(int bit = c.nextSetBit(0); bit >= 0; bit = c.nextSetBit(bit+1))
                    ret.add(bit);
                return ret;
            }
	/* Project selection: s->v with cap p if p > 0. v->t with -p if p < 0
	if w is preReq of v, then v->w with cap INF. Revenue is sum of positive
	revenues minus max flow. Projects taken is bfs() with dist[i] == -1
	Image seg: s->i with cap = value of being on source side. i->t with value
	of being on sink side. i<->j with penalty of i and j in separate groups
	if s->i saturated, then i is on sink side and vice versa
	bfs() with dist[i] == -1 means 'i' is on source side. Total value
	is sum of values of both sides minus max flow
	*/
        }
    }

    static void ruffleSort(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSort(long[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            long temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
        Arrays.sort(a);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}