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

public class Main {

    private static boolean matrix_exist(int a, int b,
                                        int r, int c) {
        int row_sum = 0;
        int column_sum = 0;
        int row_max = -1;
        int column_max = -1;
        int row_non_zero = 0;
        int column_non_zero = 0;

        for (int i = 0; i < r; i++) {
            row_sum += a;
            row_max = Math.max(row_max, a);
            if (a > 0) {
                row_non_zero++;
            }
        }

        for (int i = 0; i < c; i++) {
            column_sum += b;
            column_max = Math.max(column_max, b);
            if (b > 0) {
                column_non_zero++;
            }
        }

        return (row_sum == column_sum)
                && (row_max <= column_non_zero)
                && (column_max <= row_non_zero);
    }

    public static char[][] findIt(int n, int m, int a, int b) {
        char[][] ans = new char[n][m];
        int[] howC = new int[m];
        Arrays.fill(howC, b);
        for (int i = 0; i < n; i++) {
            int howR = a;
            for (int j = 0; j < m; j++) {
                if (howR > 0 && howC[j] > 0) {
                    howR--;
                    howC[j]--;
                    ans[i][j] = '1';
                } else ans[i][j] = '0';
            }
            if (howR > 0) return null;
        }
        for (int i = 0; i < m; i++) if (howC[i] > 0) return null;
        return ans;
    }

    public static void main(String[] args) throws Exception {
        ScanReader in = new ScanReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int query = in.scanInt();
        out:
        for (int test = 1; test <= query; test++) {
            int n = in.scanInt();
            int m = in.scanInt();
            int a = in.scanInt();
            int b = in.scanInt();
            if (!matrix_exist(a, b, n, m)) {
                out.println("NO");
                continue;
            }
            Dinic dc = new Dinic(n + m + 5, n * m + n + m + 50);
            int src = 1;
            int dest = n + m + 4;
            for (int i = 0; i < n; i++) dc.add_edge(src, i + 2, a);
            for (int j = 0; j < m; j++) dc.add_edge(n + 2 + j, dest, b);
            int[][] which = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    which[i][j] = dc.add_edge(i + 2, n + 2 + j, 1) - 1;
                }
            }
            int flow = (int) dc.dinic(src, dest);
            if (flow != a * n) throw new RuntimeException();
            char[][] ans = new char[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (dc.capacity[which[i][j]] - dc.flow[which[i][j]] == 1) {
                        ans[i][j] = '1';
                    } else ans[i][j] = '0';
                }
            }
            out.println("YES");
            for (int i = 0; i < n; i++) out.println(ans[i]);
        }
        out.close();
    }
}

class Dinic {
    public long INF = 1l << 62;
    int n;
    int m;
    int[] last_node;
    int[] prev_edge;
    int[] level;
    int[] cur_dfs;
    long[] flow;
    long[] capacity;
    int[] edge;
    int index;

    public Dinic(int n, int m) {

        this.n = n;
        this.m = m;
        last_node = new int[n + 1];
        prev_edge = new int[2 * m];
        level = new int[n + 1];
        cur_dfs = new int[n + 1];
        flow = new long[2 * m];
        capacity = new long[2 * m];
        edge = new int[2 * m];
        this.index = 0;
        Arrays.fill(last_node, -1);
    }

    public int add_edge(int a, int b, long weight) {
        edge[index] = b;
        capacity[index] = weight;
        prev_edge[index] = last_node[a];
        last_node[a] = index++;

        edge[index] = a;
        prev_edge[index] = last_node[b];
        //if bidirectional edges are there, just change the capacity. since all matters is difference between flow and capacity
        capacity[index] = 0;
        last_node[b] = index++;
        return index;
    }

    public long dinic(int source, int sink) {
        long temp, flow = 0;
        while (bfs(source, sink)) {
            System.arraycopy(last_node, 0, cur_dfs, 0, n);
            while ((temp = dfs(source, INF, sink)) != 0) flow += temp;
        }
        return flow;
    }

    private long dfs(int source, long inf, int sink) {
        if (source == sink) return inf;
        for (int e = cur_dfs[source]; e != -1; cur_dfs[source] = e = prev_edge[e]) {
            if (level[edge[e]] == level[source] + 1 && flow[e] < capacity[e]) {
                long res = dfs(edge[e], Math.min(inf, capacity[e] - flow[e]), sink);
                if (res > 0) {
                    flow[e] += res;
                    flow[e ^ 1] -= res;
                    return res;
                }
            }
        }
        return 0;
    }

    private boolean bfs(int source, int sink) {
        Arrays.fill(level, -1);
        int front = 0;
        int back = 0;
        int[] queue = new int[n];
        level[source] = 0;
        queue[back++] = source;
        while (front < back && level[sink] == -1) {
            int node = queue[front++];
            for (int e = last_node[node]; e != -1; e = prev_edge[e]) {
                int to = edge[e];
                if (level[to] == -1 && flow[e] < capacity[e]) {
                    level[to] = level[node] + 1;
                    queue[back++] = to;
                }
            }
        }
        return level[sink] != -1;
    }


}

class ScanReader {
    private final byte[] buf = new byte[4 * 1024];
    private final BufferedInputStream in;
    private int index;
    private int total;

    public ScanReader(InputStream inputStream) {
        in = new BufferedInputStream(inputStream);
    }

    private int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) return -1;
        }
        return buf[index++];
    }

    public char scanChar() throws IOException {
        int c = scan();
        while (isWhiteSpace(c)) c = scan();
        return (char) c;
    }


    public int scanInt() throws IOException {
        int integer = 0;
        int n = scan();
        while (isWhiteSpace(n)) n = scan();
        int neg = 1;
        if (n == '-') {
            neg = -1;
            n = scan();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = scan();
            }
        }
        return neg * integer;
    }

    public String scanString() throws IOException {
        int c = scan();
        while (isWhiteSpace(c)) c = scan();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = scan();
        } while (!isWhiteSpace(c));
        return res.toString();
    }

    private boolean isWhiteSpace(int n) {
        return n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1;
    }

    public long scanLong() throws IOException {
        long integer = 0;
        int n = scan();
        while (isWhiteSpace(n)) n = scan();
        int neg = 1;
        if (n == '-') {
            neg = -1;
            n = scan();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = scan();
            }
        }
        return neg * integer;
    }

    public void scanLong(long[] A) throws IOException {
        for (int i = 0; i < A.length; i++) A[i] = scanLong();
    }

    public void scanInt(int[] A) throws IOException {
        for (int i = 0; i < A.length; i++) A[i] = scanInt();
    }

    public double scanDouble() throws IOException {
        int c = scan();
        while (isWhiteSpace(c)) c = scan();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = scan();
        }
        double res = 0;
        while (!isWhiteSpace(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, scanInt());
            }
            res *= 10;
            res += c - '0';
            c = scan();
        }
        if (c == '.') {
            c = scan();
            double m = 1;
            while (!isWhiteSpace(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, scanInt());
                }
                m /= 10;
                res += (c - '0') * m;
                c = scan();
            }
        }
        return res * sgn;
    }

}