Problem: A system of n vessels with water is given. Several pairs of vessels are connected by tubes with transfusion mechanisms. One may transfer an integer amount of liters of water between two vessels connected by such tube (tube works in both directions). There might be multiple tubes between two vessels. Total number of tubes equals e. Volume of each vessel equals v liters. Of course, the amount of the water in any vessel cannot exceed v liters in the process of transfusions.

Given the initial amounts ai of water in the vessels and the desired amounts bi find a sequence of transfusions that deals with the task. Total number of transfusions must not exceed 2·n2.

Input

First line of the input contains integers n, v, e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000).

Next two lines contain n integers each: initial ai and the desired amounts bi of water in corresponding vessels (0 ≤ ai, bi ≤ v).

Next e lines describe one tube each in the format x y (1 ≤ x, y ≤ n, x ≠ y) for a tube between vessels number x and y. There might be multiple tubes between two vessels. You may assume that vessels are numbered from 1 to n in some way.

Output

Print "NO" (without quotes), if such sequence of transfusions does not exist.

Otherwise print any suitable sequence in the following format. On the first line print the total number of transfusions k (k should not exceed 2·n2). In the following k lines print transfusions in the format x y d (transfusion of d liters from the vessel number x to the vessel number y, x and y must be distinct). For all transfusions d must be a non-negative integer.

Examples

Input

2 10 1
1 9
5 5
1 2


Output

1
2 1 4


Input

2 10 0
5 2
4 2


Output

NO


Input

2 10 0
4 2
4 2


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <typename T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <typename T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <typename T>
inline void println(T first) {
  print(first), putchar('\n');
}
template <typename T>
inline void printsp(T first) {
  print(first), putchar(' ');
}
template <class T, class T1>
inline void print(T first, T1 second) {
  printsp(first), println(second);
}
template <class T, class T1, class T2>
inline void print(T first, T1 second, T2 z) {
  printsp(first), printsp(second), println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
vector<int> adj[333];
int root[333];
int find_root(int u) { return root[u] == u ? u : root[u] = find_root(root[u]); }
vector<pair<pair<int, int>, int> > ans;
int a[333], b[333];
int vst[333], flag[333][333];
int sz[333];
long long sa[333], sb[333];
void dfs(int u, int fa = 0) {
  vst[u] = 1;
  sz[u] = 1;
  sa[u] = a[u];
  sb[u] = b[u];
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (flag[u][v] || v == fa) continue;
    dfs(v, u);
    sz[u] += sz[v];
    sa[u] += sa[v];
    sb[u] += sb[v];
  }
}
void add(int u, int v, int k) {
  if (k) ans.push_back(pair<pair<int, int>, int>(pair<int, int>(u, v), k));
}
int LIM;
bool redfs(int u, int fa, long long A, long long B, int &U, int &V) {
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == fa || flag[u][v]) continue;
    long long pa = A - sa[v];
    long long push_back = B - sb[v];
    if (pa >= push_back && a[u] >= pa - push_back &&
        a[v] + pa - push_back <= LIM) {
      add(u, v, pa - push_back);
      a[u] -= pa - push_back;
      a[v] += pa - push_back;
      U = u;
      V = v;
      return true;
    }
    if (sa[v] >= sb[v] && a[v] >= sa[v] - sb[v] &&
        a[u] + sa[v] - sb[v] <= LIM) {
      add(v, u, sa[v] - sb[v]);
      a[u] += sa[v] - sb[v];
      a[v] -= sa[v] - sb[v];
      U = u;
      V = v;
      return true;
    }
    if (redfs(v, u, A, B, U, V)) return true;
  }
  return false;
}
void redfs(int u, int fa, long long A, long long B, int &U, int &V,
           long long &mx) {
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == fa || flag[u][v]) continue;
    long long pa = A - sa[v];
    long long push_back = B - sb[v];
    if (pa >= push_back) {
      long long mn =
          min((long long)a[u], min(pa - push_back, (long long)LIM - a[v]));
      if (mx < mn) mx = mn, U = u, V = v;
    }
    if (sa[v] >= sb[v]) {
      long long mn =
          min((long long)a[v], min(sa[v] - sb[v], (long long)LIM - a[u]));
      if (mx < mn) mx = mn, U = v, V = u;
    }
    redfs(v, u, A, B, U, V, mx);
  }
}
bool solve(int u) {
  dfs(u);
  if (sa[u] != sb[u]) return false;
  if (sz[u] == 1) return true;
  int U = 0, V = 0;
  redfs(u, 0, sa[u], sb[u], U, V);
  if (U == 0) {
    long long mx = -1;
    redfs(u, 0, sa[u], sb[u], U, V, mx);
    add(U, V, mx);
    a[U] -= mx;
    a[V] += mx;
    return solve(u);
  }
  flag[U][V] = flag[V][U] = 1;
  solve(U);
  solve(V);
  return true;
}
int main() {
  int n, m;
  gn(n, LIM, m);
  for (int i = 1; i <= n; i++) gn(a[i]);
  for (int i = 1; i <= n; i++) gn(b[i]), root[i] = i;
  for (int i = 0; i < m; i++) {
    int u, v;
    gn(u, v);
    int uu = find_root(u);
    int vv = find_root(v);
    if (uu == vv) continue;
    root[uu] = vv;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++)
    if (!vst[i]) {
      if (!solve(i)) return puts("NO"), 0;
    }
  println(ans.size());
  for (int i = 0; i < ans.size(); i++)
    print(ans[i].first.first, ans[i].first.second, ans[i].second);
  return 0;
}