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.util.*;

public class G
{
    static final boolean RUN_TIMING = false;
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        // in = new BufferedReader(new FileReader(new File("test.txt")));
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        tok = new StringTokenizer(in.readLine());
        int zzz = ipar();
        for (int zz = 0; zz < zzz; zz++)
        {
            ntok();
            int n = ipar();
            int m = ipar();
            int a = ipar();
            int b = ipar();
            char[][] mat = new char[n][m];
            for (char[] arr : mat) {
                Arrays.fill(arr, '0');
            }
            int i = 0;
            int e = 0;
            int count = 0;
            while (i < n) {
                mat[i][e] = '1';
                count++;
                if (count == a) {
                    i++;
                    count = 0;
                }
                e = (e+1)%m;
            }
            boolean works = true;
            for (i = 0; i < n; i++) {
                count = 0;
                for (e = 0; e < m; e++) {
                    if (mat[i][e] == '1') {
                        count++;
                    }
                }
                if (count != a) {
                    works = false;
                    break;
                }
            }
            for (e = 0; e < m; e++) {
                count = 0;
                for (i = 0; i < n; i++) {
                    if (mat[i][e] == '1') {
                        count++;
                    }
                }
                if (count != b) {
                    works = false;
                    break;
                }
            }
            if (works) {
                out.println("YES");
                for (char[] arr : mat) {
                    out.println(arr);
                }
            } else {
                out.println("NO");
            }
        }

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

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public int[] iapar(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public long[] lapar(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        long time = 0;
        time -= System.nanoTime();
        new G().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
    }
}
