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
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.*;

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 2e9;
    static final long OO = (long) 4e18;
    static final int MOD = 998244353;
    static final int N = (int) (5e5 + 5);

    static class Dinic {
        class Edge {
            int u, v;
            int c, f;

            Edge(int u, int v, int c) {
                this.u = u;
                this.v = v;
                this.c = c;
                f = 0;
            }
        }
        int n;
        ArrayList<Edge> edges;
        ArrayList<Integer>[] adj;
        int[] q, d, ptr;

        Dinic(int n) {
            this.n = n;
            edges = new ArrayList<>();
            adj = new ArrayList[n]; Arrays.setAll(adj, i -> new ArrayList<>());
            q = new int[n];
            d = new int[n];
            ptr = new int[n];
        }

        void addEdge(int u, int v, int c) {
            adj[u].add(edges.size());
            adj[v].add(edges.size() + 1);
            edges.add(new Edge(u, v, c));
            edges.add(new Edge(v, u, 0));
        }

        int maxFlow(int s, int t) {
            int flow = 0;
            while (bfs(s, t)) {
                Arrays.fill(ptr, 0);
                int delta;
                while ((delta = dfs(s, t, oo)) != 0)
                    flow += delta;
            }
            return flow;
        }

        boolean bfs(int s, int t) {
            int i = 0;
            q[i++] = s;
            Arrays.fill(d, oo);
            d[s] = 0;
            for (int j = 0; j < i; j++) {
                int u = q[j];
                for (int ei : adj[u]) {
                    Edge e = edges.get(ei);
                    if (d[e.v] == oo && e.f < e.c) {
                        q[i++] = e.v;
                        d[e.v] = d[u] + 1;
                    }
                }
            }
            return d[t] != oo;
        }

        int dfs(int u, int t, int minDelta) {
            if (u == t || minDelta == 0)
                return minDelta;
            for (; ptr[u] < adj[u].size(); ptr[u]++) {
                int ei = adj[u].get(ptr[u]);
                Edge e = edges.get(ei);
                if (d[e.v] == d[u] + 1) {
                    int pushed = dfs(e.v, t, Math.min(minDelta, e.c - e.f));
                    if (pushed != 0) {
                        e.f += pushed;
                        edges.get(ei ^ 1).f -= pushed;
                        return pushed;
                    }
                }
            }
            return 0;
        }
    }

    static void solve() {
        int tests = in.nextInt();

        while (tests-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();

            Dinic dinic = new Dinic(n + m + 2);
            int s = n + m, t = n + m + 1;
            for (int i = 0; i < n; i++)
                dinic.addEdge(s, i, a);
            for (int i = n; i < n + m; i++)
                dinic.addEdge(i, t, b);
            for (int i = 0; i < n; i++)
                for (int j = n; j < n + m; j++)
                    dinic.addEdge(i, j, 1);

            int maxFlow = dinic.maxFlow(s, t);
            if (maxFlow != n * a || maxFlow != m * b) {
                out.println("NO");
                continue;
            }

            out.println("YES");

            int[][] ans = new int[n][m];
            for (Dinic.Edge e : dinic.edges) {
                if (e.u < n + m && e.v < n + m && e.f == 1)
                    ans[e.u][e.v - n] = 1;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++)
                    out.print(ans[i][j]);
                out.println();
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("sometext.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));


        solve();

//        Thread thread = new Thread(null, () -> {
//            solve();
//        }, "Main", 1 << 28);
//        thread.start();
//        try {
//            thread.join();
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }


//        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }

    static void dbg(Object... args) {
        for (Object arg : args)
            out.print(arg + " ");
        out.println();
    }

}