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.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;

public class CF2_304E {
  
  static Reader sc = new Reader();
  static PrintWriter out = new PrintWriter(System.out);
  
  public static void main(String[] args) throws IOException {
    int n = sc.nextInt();
    int m = sc.nextInt();
    
    int numV = 2 + 2*n;
    GraphMaxFlow graph = new GraphMaxFlow(numV);
    // Last 2 are start and finish
    
    int[] from = new int[n];
    int[] to = new int[n];
    
    int sumFrom = 0;
    int sumTo = 0;
    
    for (int i = 0; i < n; i++) {
      from[i] = sc.nextInt();
      graph.addEdge(numV - 2, i, from[i]);
      sumFrom += from[i];
    }
    
    for (int i = 0; i < n; i++) {
      to[i] = sc.nextInt();
      graph.addEdge(n + i, numV - 1, to[i]);
      sumTo += to[i];
    }
    
    for (int i = 0; i < n; i++) {
        graph.addEdge(i, n + i, from[i]);  
    }
    
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      graph.addEdge(a, n + b, from[a]);
      graph.addEdge(b, n + a, from[b]);
    }
    
    int flow = fordFulkerson(graph, numV - 2, numV - 1);
    
    if (flow != sumTo || sumFrom != sumTo) {
      out.println("NO");
    } else {
      out.println("YES");
      
      int[][] totalFlow = new int[n][n];
      
      for (int i = 0; i < n; i++) {
        for (FlowEdge edge : graph.adjacent[i]) {
          if (edge.from == i && edge.to < 2*n) {
            totalFlow[edge.from][edge.to - n] = edge.flow;
          }
        }
      }
      
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          out.print(totalFlow[i][j] +" ");
        }
        out.println();
      }
    }
    
    out.close();
  }
  
  static int INF = Integer.MAX_VALUE / 2;
  static FlowEdge[] edgeTo;
  static boolean[] visited;

  /**
   * EdmondsKarp version of FordFulkerson's maximum flow algorithm
   * 
   * @return Maximum flow of the network given
   * @time O(|V| * |E|^2)
   * @tested UVA_820, UVA_10480, UVA_11380
   */
  static int fordFulkerson(GraphMaxFlow graph, int source, int sink) {
    int totalFlow = 0;
    edgeTo = new FlowEdge[graph.numVertices];

    while (hasAugPath(graph, source, sink)) {
      // Find minimum capacity in path from source to dest
      int min = INF;
      for (int node = sink; node != source; node = edgeTo[node].other(node)) {
        min = Math.min(min, edgeTo[node].residualCapacityTo(node));
      }
      // Increase flow in path from source to dest
      for (int node = sink; node != source; node = edgeTo[node].other(node)) {
        edgeTo[node].addResidualFlowTo(node, min);
      }
      totalFlow += min;
    }
    return totalFlow;
  }

  static boolean hasAugPath(GraphMaxFlow graph, int source, int dest) {
    visited = new boolean[graph.numVertices];

    ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
    queue.add(source);

    while (!queue.isEmpty()) {
      int node = queue.removeFirst();
      if (node == dest) {
        return true;
      }
      if (visited[node]) {
        continue;
      }
      visited[node] = true;

      for (FlowEdge edge : graph.getAdjacent(node)) {
        int next = edge.other(node);
        if (!visited[next] && edge.residualCapacityTo(next) > 0) {
          edgeTo[next] = edge;
          queue.addLast(next);
        }
      }
    }
    return false;
  }

  public boolean inSourceCut(int node) {
    return visited[node];
  }

  static class GraphMaxFlow {
    final int numVertices;
    int numEdges = 0;
    ArrayDeque<FlowEdge>[] adjacent;

    @SuppressWarnings("unchecked")
    public GraphMaxFlow(int numVertices) {
      this.numVertices = numVertices;
      adjacent = (ArrayDeque<FlowEdge>[]) new ArrayDeque[numVertices];
      for (int node = 0; node < numVertices; node++) {
        adjacent[node] = new ArrayDeque<FlowEdge>();
      }
    }

    public void addEdge(FlowEdge edge) {
      adjacent[edge.from].add(edge);
      adjacent[edge.to].add(edge);
      numEdges++;
    }

    public void addEdge(int from, int to, int capacity) {
      addEdge(new FlowEdge(from, to, capacity));
    }

    public void addUndirectedEdge(int from, int to, int capacity) {
      addEdge(new FlowEdge(from, to, capacity));
      addEdge(new FlowEdge(to, from, capacity));
    }

    public ArrayDeque<FlowEdge> getAdjacent(int node) {
      return adjacent[node];
    }

    public String toString() {
      StringBuilder sb = new StringBuilder(numVertices + numEdges);
      sb.append("Nodes: " + numVertices + " Edges: " + numEdges + "\n");
      for (int node = 0; node < numVertices; node++) {
        sb.append(node + " -> ");
        int count = 0;
        for (FlowEdge edge : getAdjacent(node)) {
          if (count != 0) {
            sb.append(", ");
          }
          sb.append(edge.toString());
          count++;
        }
        sb.append('\n');
      }
      return sb.toString();
    }
  }

  static class FlowEdge {
    final int from, to, cap;
    int flow = 0;

    public FlowEdge(int from, int to, int cap) {
      this.from = from;
      this.to = to;
      this.cap = cap;
    }

    public int other(int node) {
      if (node == from) {
        return to;
      } else {
        return from;
      }
    }

    public int residualCapacityTo(int node) {
      if (node == to) {
        return cap - flow;
      } else {
        return flow;
      }
    }

    public void addResidualFlowTo(int node, int newFlow) {
      if (node == to) {
        flow += newFlow;
      } else {
        flow -= newFlow;
      }
    }

    public String toString() {
      return "(" + from + ", " + to + ", <" + flow + "/" + cap + ">)";
    }
  }

  static class Reader {
    final private int BUFFER_SIZE = 1 << 12; private byte[] buffer; private int bufferPointer, bytesRead; private boolean eof = false;
    public Reader() {buffer = new byte[BUFFER_SIZE];bufferPointer = bytesRead = 0;}
    public boolean reachedEOF() {return eof;}
    private void fillBuffer() throws IOException {bytesRead = System.in.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) { buffer[0] = -1;eof = true;}}
    private byte read() throws IOException {if (bufferPointer == bytesRead)fillBuffer();return buffer[bufferPointer++];}
    public String next() throws IOException {StringBuilder sb = new StringBuilder();byte c;while ((c = read()) <= ' ') {if (c == -1)return null;} do {sb.append((char) c);} while ((c = read()) > ' ');if (sb.length() == 0)return null;return sb.toString();}
    public String nextLine() throws IOException {StringBuilder sb = new StringBuilder();byte c;boolean read = false;while ((c = read()) != -1) {if (c == '\n') {read = true;break;}if (c >= ' ')sb.append((char) c);}if (!read)return null;return sb.toString();}
    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 * 10L + 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;}
    public int[] nextIntArray(int n) throws IOException {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}
    public int[][] nextIntMatrix(int n, int m) throws IOException {int[][] map = new int[n][m];for (int i = 0; i < n; i++)map[i] = nextIntArray(m);return map;}
    public char[][] nextCharacterMatrix(int n) throws IOException {char[][] a = new char[n][];for (int i = 0; i < n; i++)a[i] = next().toCharArray();return a;}
    public void close() throws IOException {if (System.in == null)return;System.in.close();}
  }
  
  static void print(int[] A) {for(int i=0;i<A.length;i++){if(i!=0) out.print(' ');out.print(A[i]);}out.println();}
  static <T> void print(Iterable<T> A) {int i = 0;for(T act : A){if(i!=0)out.print(' ');out.print(act);i++;}out.println();}
  static void printPlus1(Iterable<Number> A) {int i = 0;for(Number act : A){if(i!=0)out.print(' ');out.print(act.longValue() + 1L);i++;}out.println();}
  static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); }
  
  /*
    long s = System.currentTimeMillis();
    debug(System.currentTimeMillis()-s+"ms");
   */
}