You are given four positive integers n, m, a, b (1 ≤ b ≤ n ≤ 50; 1 ≤ a ≤ m ≤ 50). Find any such rectangular matrix of size n × m that satisfies all of the following conditions:

  * each row of the matrix contains exactly a ones; 
  * each column of the matrix contains exactly b ones; 
  * all other elements are zeros. 



If the desired matrix does not exist, indicate this.

For example, for n=3, m=6, a=2, b=1, there exists a matrix satisfying the conditions above:

$$$ \begin{vmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\\ 1 & 0 & 0 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 0 & 1 & 0 \end{vmatrix} $$$

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

Each test case is described by four positive integers n, m, a, b (1 ≤ b ≤ n ≤ 50; 1 ≤ a ≤ m ≤ 50), where n and m are the sizes of the matrix, and a and b are the number of ones for rows and columns, respectively.

Output

For each test case print:

  * "YES" (without quotes) and the required matrix (if there are several answers, print any) if it exists, or 
  * "NO" (without quotes) if it does not exist. 



To print the matrix n × m, print n rows, each of which consists of m numbers 0 or 1 describing a row of the matrix. Numbers must be printed without spaces.

Example

Input


5
3 6 2 1
2 2 2 1
2 2 2 2
4 4 2 2
2 1 1 2


Output


YES
010001
100100
001010
NO
YES
11
11
YES
1100
1100
0011
0011
YES
1
1
#include <bits/stdc++.h>
using namespace std;
constexpr long long INF = 2e18;
constexpr long long MOD = 1e9 + 7;
constexpr long long MAXN = 2e5 + 3;
struct Dinic {
  struct FlowEdge {
    long long v, rev, c, cap;
    bool is_rev;
    FlowEdge() {}
    FlowEdge(long long v, long long c, long long cap, long long rev,
             bool is_rev)
        : v(v), c(c), cap(cap), rev(rev), is_rev(is_rev) {}
  };
  vector<vector<FlowEdge>> adj;
  vector<long long> level, used;
  long long src, snk, V;
  long long sz;
  long long max_flow;
  bool calculated;
  Dinic() {}
  Dinic(long long n) {
    calculated = false;
    src = 0;
    snk = n + 1;
    adj.resize(n + 2, vector<FlowEdge>());
    level.resize(n + 2);
    used.resize(n + 2);
    sz = n + 2;
    V = n + 2;
    max_flow = 0;
  }
  void add_edge(long long u, long long v, long long c) {
    long long id1 = adj[u].size();
    long long id2 = adj[v].size();
    adj[u].push_back(FlowEdge(v, c, c, id2, false));
    adj[v].push_back(FlowEdge(u, 0, 0, id1, true));
  }
  void add_to_src(long long v, long long c) {
    adj[src].push_back(FlowEdge(v, c, c, -1, false));
  }
  void add_to_snk(long long u, long long c) {
    adj[u].push_back(FlowEdge(snk, c, c, -1, false));
  }
  bool bfs() {
    for (long long i = 0; i < sz; i++) {
      level[i] = -1;
    }
    level[src] = 0;
    queue<long long> q;
    q.push(src);
    while (!q.empty()) {
      long long cur = q.front();
      q.pop();
      for (FlowEdge e : adj[cur]) {
        if (level[e.v] == -1 && e.c > 0) {
          level[e.v] = level[cur] + 1;
          q.push(e.v);
        }
      }
    }
    return (level[snk] == -1 ? false : true);
  }
  long long send_flow(long long u, long long flow) {
    if (u == snk) return flow;
    for (long long &i = used[u]; i < adj[u].size(); i++) {
      FlowEdge &e = adj[u][i];
      if (level[u] + 1 != level[e.v] || e.c <= 0) continue;
      long long new_flow = min(flow, e.c);
      long long adjusted_flow = send_flow(e.v, new_flow);
      if (adjusted_flow > 0) {
        e.c -= adjusted_flow;
        if (e.rev != -1) adj[e.v][e.rev].c += adjusted_flow;
        return adjusted_flow;
      }
    }
    return 0;
  }
  long long calculate() {
    if (src == snk) {
      max_flow = -1;
      return -1;
    }
    max_flow = 0;
    while (bfs()) {
      for (long long i = 0; i < sz; i++) used[i] = 0;
      while (long long inc = send_flow(src, INF)) max_flow += inc;
    }
    calculated = true;
    return max_flow;
  }
  vector<pair<long long, long long>> mincut(
      vector<vector<long long>> &mat_adj) {
    assert(calculated);
    long long mat[sz][sz];
    memset(mat, 0, sizeof mat);
    for (long long i = 0; i < V; i++)
      for (FlowEdge x : adj[i]) mat[i][x.v] += x.c;
    vector<bool> vis(sz);
    queue<long long> q;
    q.push(src);
    vis[src] = true;
    while (!q.empty()) {
      long long u = q.front();
      q.pop();
      for (long long v = 0; v < sz; v++) {
        if (mat[u][v] > 0 && !vis[v]) {
          q.push(v);
          vis[v] = true;
        }
      }
    }
    vector<pair<long long, long long>> cut;
    for (long long i = 0; i < sz; i++)
      for (long long j = 0; j < sz; j++)
        if (vis[i] && !vis[j])
          if (mat_adj[i][j] > 0) cut.emplace_back(i, j);
    return cut;
  }
  vector<pair<long long, long long>> min_edge_cover() {
    bool covered[sz];
    for (long long i = 0; i < sz; i++) covered[i] = false;
    vector<pair<long long, long long>> edge_cover;
    for (long long i = 1; i < sz - 1; i++) {
      for (FlowEdge e : adj[i]) {
        if (e.cap == 0 || e.v > sz - 2) continue;
        if (e.c == 0) {
          edge_cover.push_back(pair<long long, long long>(i, e.v));
          covered[i] = true;
          covered[e.v] = true;
          break;
        }
      }
    }
    for (long long i = 1; i < sz - 1; i++) {
      for (FlowEdge e : adj[i]) {
        if (e.cap == 0 || e.v > sz - 2) continue;
        if (e.c == 0) continue;
        if (!covered[i] || !covered[e.v]) {
          edge_cover.push_back(pair<long long, long long>(i, e.v));
          covered[i] = true;
          covered[e.v] = true;
        }
      }
    }
    return edge_cover;
  }
  vector<vector<long long>> allFlow() {
    assert(calculated);
    vector<vector<long long>> ret(V, vector<long long>(V, 0));
    for (long long i = 0; i < V; i++) {
      for (FlowEdge x : adj[i]) {
        if (x.is_rev) continue;
        ret[i][x.v] += x.cap - x.c;
      }
    }
    return ret;
  }
  void dfs_build_path(long long u, vector<long long> &path,
                      vector<vector<long long>> &mat_flow,
                      vector<vector<long long>> &ans,
                      vector<vector<long long>> &adj) {
    path.push_back(u);
    if (u == this->snk) {
      ans.push_back(path);
      return;
    }
    for (long long v : adj[u]) {
      if (mat_flow[u][v]) {
        mat_flow[u][v]--;
        dfs_build_path(v, path, mat_flow, ans, adj);
        return;
      }
    }
  }
  vector<vector<long long>> get_all_paths(vector<vector<long long>> &adj) {
    assert(calculated);
    vector<vector<long long>> mat_flow = allFlow();
    vector<vector<long long>> ans;
    ans.reserve(max_flow);
    for (long long i = 0; i < max_flow; i++) {
      vector<long long> path;
      path.reserve(V);
      dfs_build_path(this->src, path, mat_flow, ans, adj);
    }
    return ans;
  }
};
long long conv(long long i, long long j, long long m) { return i * m + j; }
void solve() {
  long long n;
  cin >> n;
  long long m;
  cin >> m;
  long long a, b;
  cin >> a >> b;
  long long qtd = n + m;
  Dinic d(n + m);
  for (long long i = 1; i <= n; ++i) {
    d.add_to_src(i, a);
  }
  for (long long i = n + 1; i <= n + m; ++i) d.add_to_snk(i, b);
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 1; j <= m; ++j) {
      d.add_edge(i, j + n, 1);
    }
  }
  d.calculate();
  auto v = d.allFlow();
  vector<vector<long long>> mat =
      vector<vector<long long>>(n, vector<long long>(m, 0));
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 1; j <= m; ++j) {
      mat[i - 1][j - 1] = v[i][j + n];
    }
  }
  vector<long long> r(n), c(m);
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < m; ++j) {
      r[i] += mat[i][j];
      c[j] += mat[i][j];
    }
  }
  for (long long x : r) {
    if (x != a) {
      cout << "NO" << '\n';
      return;
    }
  }
  for (long long x : c) {
    if (x != b) {
      cout << "NO" << '\n';
      return;
    }
  }
  cout << "YES" << '\n';
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < m; ++j) {
      cout << mat[i][j];
    }
    cout << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) solve();
}
