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 codeforces {
    static class pair {
        int x;
        int y;

        public pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static long sqrt(long x) {
        long s = 0, e = x, root = 0;
        while (s <= e) {
            long mid = (s + e) / 2;
            if (mid * mid == x)
                return mid;
            if (mid * mid < x) {
                root = mid;
                s = mid + 1;
            } else
                e = mid - 1;
        }
        return root;
    }

    public static long power(long a, long b) {
        if (a == 0 || b == 0)
            return 1L;
        long ans = power(a, b / 2);
        ans *= ans;
        if (b % 2 == 1)
            ans *= a;
        return ans;
    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static boolean isSubsequence(String a, String b) {
        int m = a.length(), n = b.length(), i = 0, j = 0;
        while (i < m && j < n) {
            if (a.charAt(i) == b.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == m;
    }

    public static boolean isprime(long x) {
        if (x == 1)
            return false;
        if (x < 4)
            return true;
        int root = (int) Math.sqrt(x);
        for (int i = 2; i <= root; i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }

    public static long longmax(long a, long b) {
        return Math.max(a, b);
    }

    public static long longmin(long a, long b) {
        return Math.min(a, b);
    }

    public static int intmax(int a, int b) {
        return Math.max(a, b);
    }

    public static int intmin(int a, int b) {
        return Math.min(a, b);
    }

    public static void rev(char[] ch) {
        int s = 0, e = ch.length - 1;
        while (s < e) {
            char c = ch[s];
            ch[s] = ch[e];
            ch[e] = c;
            s++;
            e--;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder str = new StringBuilder();
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            // int n=Integer.parseInt(br.readLine());
            String[] lol = br.readLine().split(" ");
            int n = Integer.parseInt(lol[0]), m = Integer.parseInt(lol[1]), a = Integer.parseInt(lol[2]),
                    b = Integer.parseInt(lol[3]);
            if (n * a == m * b) {
                str.append("YES\n");
                int[][] arr = new int[n][m];
                int s = 0;
                for (int i = 0; i < n; i++) {
                    for (int j = s; j < s + a; j++)
                        arr[i][j % m] = 1;
                    s += a;
                }
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        str.append(arr[i][j]);
                    }
                    str.append("\n");
                }
            } else
                str.append("NO\n");

            // long n=Long.parseLong(lol[0]),k=Long.parseLong(lol[1]);
            // int a=Integer.parseInt(lol[0]),b=Integer.parseInt(lol[1]);
            // int[] a=new int[n];

            // int[] freq=new int[n+1];
            // boolean[] vis=new boolean[n+1];
            // Arrays.sort(a);

        }
        out.print(str);
        out.close();
    }
}