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.BufferedWriter;
import java.util.InputMismatchException;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
import java.util.Arrays;
import java.util.AbstractList;
import java.io.InputStream;
import java.util.Locale;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.AbstractCollection;
import java.util.RandomAccess;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Jacob Jiang
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = in.nextIntArray(n);
        int[] b = in.nextIntArray(n);
        long sum = ArrayUtils.sum(a);
        if (sum != ArrayUtils.sum(b)) {
            out.println("NO");
            return;
        }
        Graph graph = new ListGraph(2 * n + 2);
        for (int i = 0; i < n; i++) {
            graph.addEdge(new FlowEdge(0, i + 1, a[i]));
            graph.addEdge(new FlowEdge(n + i + 1, 2 * n + 1, b[i]));
            graph.addEdge(new FlowEdge(i + 1, i + n + 1, Long.MAX_VALUE));
        }
        for (int i = 0; i < m; i++) {
            int p = in.nextInt();
            int q = in.nextInt();
            graph.addEdge(new FlowEdge(p, q + n, Long.MAX_VALUE));
            graph.addEdge(new FlowEdge(q, p + n, Long.MAX_VALUE));
        }
        long maxFlow = GraphAlgorithms.maxFlowEdmondsKarp(graph, 0, 2 * n + 1);
        if (maxFlow == sum) {
            out.println("YES");
            long[][] answer = new long[n][n];
            for (int i = 1; i <= n; i++) {
                for (Edge edge : graph.getConnectedEdges(i)) {
                    if (edge.getDestination() > n && edge.getDestination() <= 2 * n) {
                        answer[i - 1][edge.getDestination() - n - 1] = edge.getReverseEdge().getCapacity();
                    }
                }
            }
            for (long[] longs : answer) {
                out.printLine(longs);
            }
        } else {
            out.println("NO");
        }
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 16];
    private int curChar;
    private int numChars;
    private SpacePredicate spacePredicate;
    private boolean used = false;

    public static interface SpacePredicate {
        public boolean isSpaceChar(int c);
    }

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        used = true;
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public static boolean isSpaceCharDefault(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public boolean isSpaceChar(int c) {
        if (spacePredicate == null)
            return isSpaceCharDefault(c);
        else
            return spacePredicate.isSpaceChar(c);
    }

    public int[] nextIntArray(int count) {
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextInt();
        }
        return result;
    }

}

class OutputWriter {
    private PrintWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
    }

    public OutputWriter print(long l) {
        writer.print(l);
        return this;
    }

    public OutputWriter println() {
        writer.println();
        return this;
    }

    public OutputWriter println(String x) {
        writer.println(x);
        return this;
    }

    public OutputWriter print(char c) {
        writer.print(c);
        return this;
    }

    public void close() {
        writer.close();
    }

    public OutputWriter printItems(long[] items) {
        for (int i = 0; i < items.length; i++) {
            if (i != 0) {
                print(' ');
            }
            print(items[i]);
        }
        return this;
    }

    public OutputWriter printLine(long[] items) {
        printItems(items);
        println();
        return this;
    }

}

class ArrayUtils {

    public static long sum(int[] a) {
        long result = 0;
        for (int i : a) {
            result += i;
        }
        return result;
    }


}

interface Graph {
    int getVertexCount();

    List<Edge> getConnectedEdges(int vertexIndex);

    void addEdge(Edge edge);

}

class ListGraph extends AbstractGraph {
    protected List<List<Edge>> edgeLists;
    int vertexCount;
    boolean fixedVertexCount;

    public ListGraph(int vertexCount, boolean fixedVertexCount) {
        if (vertexCount < 0)
            throw new IllegalArgumentException("vertexCount < 0, " + vertexCount);
        this.vertexCount = vertexCount;
        this.fixedVertexCount = fixedVertexCount;
        edgeLists = new ArrayList<List<Edge>>(vertexCount);
        for (int i = 0; i < vertexCount; i++) {
            edgeLists.add(new ArrayList<Edge>());
        }
    }

    public ListGraph(int vertexCount) {
        this(vertexCount, true);
    }

    public int getVertexCount() {
        return vertexCount;
    }

    protected void ensureListSize(int size) {
        if (size < 0)
            throw new IllegalArgumentException("size < 0, " + size);
        if (fixedVertexCount && size > vertexCount) {
            throw new RuntimeException("vertexCount is fixed.");
        }
        while (edgeLists.size() < size) {
            edgeLists.add(new ArrayList<Edge>());
        }
        vertexCount = Math.max(vertexCount, size);
    }

    protected boolean isValidVertexIndex(int vertexIndex) {
        if (fixedVertexCount)
            return vertexIndex >= 0 && vertexIndex < vertexCount;
        else
            return vertexIndex >= 0;
    }

    public List<Edge> getConnectedEdges(int vertexIndex) {
        return new ArrayList<Edge>(edgeLists.get(vertexIndex));
    }

    public void addEdge(Edge edge) {
        if (!isValidVertexIndex(edge.getSource()) || !isValidVertexIndex(edge.getDestination())) {
            throw new IllegalArgumentException("vertex index illegal");
        }
        ensureListSize(edge.getSource() + 1);
        ensureListSize(edge.getDestination() + 1);
        edgeLists.get(edge.getSource()).add(edge);
        Edge reverseEdge = edge.getReverseEdge();
        if (reverseEdge != null) {
            edgeLists.get(reverseEdge.getSource()).add(reverseEdge);
        }
    }

}

interface Edge {
    int getSource();

    int getDestination();

    long getCapacity();

    void pushFlow(long flow);

    Edge getReverseEdge();
}

class FlowEdge extends BidirectionalEdge {
    protected long capacity;
    protected long reverseCapacity;
    public FlowEdge(int source, int destination, long capacity) {
        super(source, destination, true);
        if (capacity > 0) {
            this.capacity = capacity;
            this.reverseCapacity = 0;
        } else {
            this.capacity = 0;
            this.reverseCapacity = -capacity;
        }
        this.reverseEdge = new FlowReverseEdge();
    }

    public long getCapacity() {
        return capacity;
    }

    public void pushFlow(long flow) {
        capacity -= flow;
        reverseCapacity += flow;
        if (capacity < 0 || reverseCapacity < 0) {
            throw new RuntimeException("capacity < 0 || reverseCapacity < 0");
        }
    }

    protected class FlowReverseEdge extends BidirectionalEdge.ReverseEdge {

        public long getCapacity() {
            return reverseCapacity;
        }

    }
}

class GraphAlgorithms {

    public static long maxFlowEdmondsKarp(Graph graph, int source, int sink) {
        if (source == sink) {
            throw new RuntimeException("source == sink");
        }
        int vertexCount = graph.getVertexCount();
        boolean[] visited = new boolean[vertexCount];
        int[] queue = new int[vertexCount];
        Edge[] previous = new Edge[vertexCount];
        long result = 0;
        while (true) {
            Arrays.fill(visited, false);
            visited[source] = true;
            previous[sink] = null;
            int queueHead = 0;
            queue[queueHead++] = source;
            tag:
            for (int i = 0; i < queueHead; i++) {
                int cur = queue[i];
                for (Edge edge : graph.getConnectedEdges(cur)) {
                    if (edge.getCapacity() > 0 && !visited[edge.getDestination()]) {
                        visited[edge.getDestination()] = true;
                        previous[edge.getDestination()] = edge;
                        if (edge.getDestination() == sink) {
                            break tag;
                        }
                        queue[queueHead++] = edge.getDestination();
                    }
                }
            }
            if (previous[sink] == null) {
                break;
            }
            long flow = Long.MAX_VALUE;
            int cur = sink;
            while (cur != source) {
                flow = Math.min(flow, previous[cur].getCapacity());
                cur = previous[cur].getSource();
            }
            result += flow;
            cur = sink;
            while (cur != source) {
                previous[cur].pushFlow(flow);
                cur = previous[cur].getSource();
            }
        }
        return result;
    }
}

abstract class AbstractGraph implements Graph {

}

class BidirectionalEdge extends AbstractEdge {
    protected int source;
    protected int destination;
    protected Edge reverseEdge;

    protected BidirectionalEdge(int source, int destination, boolean dummy) {
        this.source = source;
        this.destination = destination;
    }

    public int getSource() {
        return source;
    }

    public int getDestination() {
        return destination;
    }

    public Edge getReverseEdge() {
        return reverseEdge;
    }

    protected class ReverseEdge extends AbstractEdge {

        public int getSource() {
            return destination;
        }

        public int getDestination() {
            return source;
        }

        public long getWeight() {
            return BidirectionalEdge.this.getWeight();
        }

        public int getIndex() {
            return BidirectionalEdge.this.getIndex();
        }

        public boolean getTag() {
            return BidirectionalEdge.this.getTag();
        }

        public Object getInfo() {
            return BidirectionalEdge.this.getInfo();
        }

        public void setWeight(long weight) {
            BidirectionalEdge.this.setWeight(weight);
        }

        public void setTag(boolean tag) {
            BidirectionalEdge.this.setTag(tag);
        }

        public void toggleTag() {
            BidirectionalEdge.this.toggleTag();
        }

        public Edge getReverseEdge() {
            return BidirectionalEdge.this;
        }

        public void pushFlow(long flow) {
            BidirectionalEdge.this.pushFlow(-flow);
        }
    }

}

abstract class AbstractEdge implements Edge {
    public long getWeight() {
        return 1;
    }

    public long getCapacity() {
        return 0;
    }

    public int getIndex() {
        throw new UnsupportedOperationException();
    }

    public boolean getTag() {
        return false;
    }

    public Object getInfo() {
        return null;
    }

    public void setWeight(long weight) {
        throw new UnsupportedOperationException();
    }

    public void setTag(boolean tag) {
        throw new UnsupportedOperationException();
    }

    public void toggleTag() {
        setTag(!getTag());
    }

    public void pushFlow(long flow) {
        throw new UnsupportedOperationException();
    }

    public Edge getReverseEdge() {
        return null;
    }

}