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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x546E
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         int[] brr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            brr[i] = Integer.parseInt(st.nextToken());
         ArrayDeque<Integer>[] edges = new ArrayDeque[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new ArrayDeque<Integer>();
         for(int i=0; i < M; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);  edges[b].add(a);
         }
         MaxFlow mfmc = new MaxFlow(2*N+2, 2*N+1, 2*N+2);
         for(int v=1; v <= N; v++)
         {
            mfmc.addEdge(v, N+v, Long.MAX_VALUE/2);
            for(int b: edges[v])
               if(v < b)
               {
                  mfmc.addEdge(v, N+b, Long.MAX_VALUE/2);
                  mfmc.addEdge(b, N+v, Long.MAX_VALUE/2);
               }
         }
         for(int v=1; v <= N; v++)
         {
            mfmc.addEdge(2*N+1, v, arr[v-1]);
            mfmc.addEdge(N+v, 2*N+2, brr[v-1]);
         }
         long flow = mfmc.mfmc();
         if(flow == sum(arr) && flow == sum(brr))
         {
            StringBuilder sb = new StringBuilder("YES\n");
            long[][] grid = new long[N+1][N+1];
            for(int a=1; a <= N; a++)
               for(MaxFlow.Edge e: mfmc.edges[a])
                  if(e.flow > 0 && e.to <= 2*N)
                     grid[a][e.to-N] = e.flow;
            for(int a=N+1; a <= 2*N; a++)
               for(MaxFlow.Edge e: mfmc.edges[a])
                  if(e.flow > 0 && e.to <= N)
                     grid[a-N][e.to] = e.flow;
            for(int a=1; a <= N; a++)
            {
               for(int b=1; b <= N; b++)
                  sb.append(grid[a][b]+" ");
               sb.append("\n");
            }
            System.out.print(sb);
         }
         else
            System.out.println("NO");
      }
      public static long sum(int[] arr)
      {
         long res = 0L;
         for(int x: arr)
            res += x;
         return res;
      }
   }
   class MaxFlow
   {
      public int N, source, sink;
      public ArrayList<Edge>[] edges;
      private int[] depth;
      
      public MaxFlow(int n, int x, int y)
      {
         N = n;
         source = x;
         sink = y;
         edges = new ArrayList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new ArrayList<Edge>();
         depth = new int[N+1];
      }
      public void addEdge(int from, int to, long cap)
      {
         Edge forward = new Edge(from, to, cap);
         Edge backward = new Edge(to, from, 0L);
         forward.residual = backward;
         backward.residual = forward;
         edges[from].add(forward);
         edges[to].add(backward);
      }
      public long mfmc()
      {
         long res = 0L;
         int[] magic = new int[N+1];
         while(assignDepths())
         {
            long flow = dfs(source, Long.MAX_VALUE/2, magic);
            while(flow > 0)
            {
               res += flow;
               flow = dfs(source, Long.MAX_VALUE/2, magic);
            }
            magic = new int[N+1];
         }
         return res;
      }
      private boolean assignDepths()
      {
         Arrays.fill(depth, -69);
         ArrayDeque<Integer> q = new ArrayDeque<Integer>();
         q.add(source);
         depth[source] = 0;
         while(q.size() > 0)
         {
            int curr = q.poll();
            for(Edge e: edges[curr])
               if(e.capacityLeft() > 0 && depth[e.to] == -69)
               {
                  depth[e.to] = depth[curr]+1;
                  q.add(e.to);
               }
         }
         return depth[sink] != -69;
      }
      private long dfs(int curr, long bottleneck, int[] magic)
      {
         if(curr == sink)
            return bottleneck;
         for(; magic[curr] < edges[curr].size(); magic[curr]++)
         {
            Edge e = edges[curr].get(magic[curr]);
            if(e.capacityLeft() > 0 && depth[e.to]-depth[curr] == 1)
            {
               long val = dfs(e.to, Math.min(bottleneck, e.capacityLeft()), magic);
               if(val > 0)
               {
                  e.augment(val);
                  return val;
               }
            }
         }
         return 0L;  //no flow
      }
      public class Edge
      {
         public int from, to;
         public long flow, capacity;
         public Edge residual;
         
         public Edge(int f, int t, long cap)
         {
            from = f;
            to = t;
            capacity = cap;
         }
         public long capacityLeft()
         {
            return capacity-flow;
         }
         public void augment(long val)
         {
            flow += val;
            residual.flow -= val;
         }
      }
   }