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

//1360G
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class A_B_Matrix {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String test_numS = bf.readLine();
        int test_num = Integer.parseInt(test_numS);
        while (test_num > 0) {
            String NandMandAandB = bf.readLine();
            String nmab[]=NandMandAandB.split(" ");
            int n=Integer.parseInt(nmab[0]);
            int m=Integer.parseInt(nmab[1]);
            int a=Integer.parseInt(nmab[2]);
            int b=Integer.parseInt(nmab[3]);
            solve3(n,m,a,b);
            test_num--;
        }
    }
    public static void solve(int n,int m,int a,int b) {
        int arr[][] = new int[n][m];
        int locx = 0, locy = 0;
        int i = locx;
        /*if (a>m/2&&b!=m){
            System.out.println("NO");
            return;
        }*/
        try {
            while (i<locx+b&&i<n){
                int j=locy;
                while (j<locy+a&&j<m){
                    arr[i][j]=1;
                    j++;
                }
                i++;
                if (i==locx+b&&(locx+b)<n){
                    locx+=b;
                    locy+=a;
                }
            }
            if (locy+a<m){
                System.out.println("NO"+"2");
                return;
            }
        }catch (ArrayIndexOutOfBoundsException e){
            System.out.println("NO"+"1");
            return;
        }

        /*for (int i = locx; i <locx+b ; i++) {
            for (int j = locy; j <locy+a ; j++) {
                arr[i][j]=1;
            }
            if (i==locx+b){
                locx+=b;
                locy+=a;
            }
        }*/
        System.out.println("YES");
        for (int k = 0; k <n ; k++) {
            for (int j = 0; j <m ; j++) {
                System.out.print(arr[k][j]);
            }
            System.out.println();
        }
    }
    public static void solve2(int n,int m,int a,int b){
        int arr[][] = new int[n][m];
        int locx = 0, locy = 0;

        for (int j = 0; j <n ; j++) {
            for (int k = locx;k<locx+a&&k <m ; k++) {
                arr[j][k]=1;
            }
            if (locx<=m-1&&(a-b+1)>0){
                locx+=a-b+1;
            }else locx+=a;
        }
        int num=0;
        for (int i = 0; i <m ; i++) {
            if (arr[n-1][i]==1){
                num++;
            }
        }
        int last_need=a-num;
        for (int i = n-1; i >0 ; i--) {
            int temp_need=last_need;
            int temp_j=0;
            while (temp_need>0){
                arr[i][temp_j++]=1;
                temp_need--;
            }
            last_need--;
        }
        if (n*a!=m*b){
            System.out.println("No");
            return;
        }
        System.out.println("YES");
        for (int k = 0; k <n ; k++) {
            for (int j = 0; j <m ; j++) {
                System.out.print(arr[k][j]);
            }
            System.out.println();
        }
    }
    public static void solve3(int n,int m,int a,int b){
        int arr[][] = new int[n][m];
        int loc=0;
        if (n*a!=m*b){
            System.out.println("No");
            return;
        }
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <a ; j++) {
                arr[i][loc]=1;
                loc=(loc+1)%m;
            }
        }

        System.out.println("YES");
        String out[]=new String[n];
        for (int i = 0; i <n ; i++) {
            StringBuffer str5 = new StringBuffer();
            for (int r : arr[i]) {
                str5.append(r);
            }
             out[i]=str5.toString();
        }
        for (int i = 0; i <n ; i++) {
            System.out.println(out[i]);
        }
    }
}
