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
/**
 * @author egaeus
 * @mail sebegaeusprogram@gmail.com
 * @veredict T.L.E.
 * @url <https://codeforces.com/problemset/problem/1360/G>
 * @category flow
 * @date 24/05/2020
 **/

import java.io.*;
import java.util.*;

import static java.lang.Integer.*;
import static java.lang.Math.*;

public class CF1360G {

    public static void main(String args[]) throws Throwable {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            int N = parseInt(st.nextToken()), M = parseInt(st.nextToken()),
                    A = parseInt(st.nextToken()), B = parseInt(st.nextToken());
            int[][] cap = new int[N + M + 2][N + M + 2];
            int s = cap.length - 2, d = cap.length - 1;
            for (int i = 0; i < N; i++) {
                cap[s][i] = A;
                for (int j = 0; j < M; j++) {
                    cap[N + j][d] = B;
                    cap[i][N + j] = 1;
                }
            }
            if (A * N == M * B) {
                sb.append("YES\n");
                char[][] result = new char[N][M];
                for (char[] a : result) Arrays.fill(a, '0');
                for (int i = 0, f = 0; i < N; i++) {
                    for (int j = 0; j < A; j++)
                        result[i][(j + f) % M] = '1';
                    f = (f + M - A) % M;
                }
                for (char[] a : result)
                    sb.append(new String(a)).append("\n");
                /*int f = edmondsKarp(cap, s, d, cap.length);
                if (A * N == f) {
                    sb.append("YES\n");
                    char[][] result = new char[N][M];
                    for (char[] a : result) Arrays.fill(a, '0');
                    for (int i = 0; i < N; i++)
                        for (int j = 0; j < M; j++)
                            if (flow[i][N+j] == 1)
                                result[i][j] = '1';
                    for (char[] a : result)
                        sb.append(new String(a)).append("\n");
                } else
                    sb.append("NO\n");*/
            } else
                sb.append("NO\n");

        }
        System.out.print(new String(sb));
    }

    static int[][] flow;

    static int edmondsKarp(int[][] capacity, int v1, int v2, int n) { // residualCapacity=capacity-flow
        int lAdy[][] = new int[n][], ants[] = new int[n], queue[] = new int[n], v, u;
        int f = 0, m, minCap[] = new int[n];
        flow = new int[n][n];
        List h[] = new List[n];
        for (u = 0; u < n; u++) h[u] = new ArrayList<Integer>();
        for (u = 0; u < n; u++)
            for (v = 0; v < n; v++)
                if (capacity[u][v] > 1e-10) {
                    h[u].add(v);
                    h[v].add(u);
                }
        for (u = 0; u < n; u++) lAdy[u] = toArr(h[u]);
        for (; (m = bfsEK(capacity, flow, lAdy, ants, minCap, queue, v1, v2)) > 1e-10; f += m)
            for (v = v2, u = ants[v]; v != v1; v = u, u = ants[v]) {
                flow[u][v] += m;
                flow[v][u] -= m;
            }
        return f;
    }

    static int bfsEK(int[][] capacity, int[][] flow, int[][] lAdy,
                     int[] ants, int[] minCap, int[] queue, int v1, int v2) {
        int i, t = 0, u;
        int z;
        Arrays.fill(ants, -1);
        ants[v1] = -2;
        minCap[v1] = 3000;
        for (queue[t++] = v1, i = 0; i < t; i++)
            for (int v : lAdy[u = queue[i]])
                if ((z = capacity[u][v] - flow[u][v]) > 1e-10 && ants[v] == -1) {
                    ants[v] = u;
                    minCap[v] = Math.min(minCap[u], z);
                    if (v == v2) return minCap[v2];
                    queue[t++] = v;
                }
        return 0;
    }

    static int[] toArr(List<Integer> p) {
        int r[] = new int[p.size()], i = 0;
        for (int x : p) r[i++] = x;
        return r;
    }
}

