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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;

public class d extends PrintWriter{
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    // static Scanner s=new Scanner(System.in);
    d() { super(System.out); }

    public static void main(String[] args) throws IOException{
        d d1=new d();d1.main();d1.flush();
    }char[] op;int[] ii,jj;int cnt;
      void main() throws IOException {
          StringBuilder sb = new StringBuilder();PrintWriter out = new PrintWriter(System.out);
         String[] s=s();
         int t=i(s[0]);
         while(t-->0) {
             String[] s2=s();
             int n=i(s2[0]);int m=i(s2[1]);int a=i(s2[2]);int b=i(s2[3]);int [][] ans=new int[n][m];
            {int x=0;
                 for(int i=0;i<n;i++){
                     if(x>=m) x=x%m;int count=0;
                     for(int j=x;;j++){
                         if(j>=m) j=j%m;
                         ans[i][j]=1;count++;
                         if(count==a) break;
                         if(j>=m) j=j%m;
                     }x+=a;
                 }int flag=0;for(int j=0;j<m;j++){
                     int count=0;for(int i=0;i<n;i++){

                         if(ans[i][j]==1) count++;
                     }if(count!=b){
                         flag=1;break;
                     }
                 }
                 if(flag==1){
                     println("NO");
                 }else{flag=0;
                     for(int i=0;i<n;i++){int count=0;
                         for(int j=0;j<m;j++){
                             if(ans[i][j]==1) count++;
                         }if(count!=a){
                             flag=1;break;
                         }
                     }if(flag==1) println("NO");else{
                     println("YES");
                     for(int i=0;i<n;i++){
                         for(int j=0;j<m;j++){
                             print(ans[i][j]);
                         }println();
                     }}
                 }
             }
         }
     }
    static String[] s() throws IOException {

        return s.readLine().trim().split("\\s+");
    }

    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }static int MAXN;
    static int[] spf;
    static void sieve() {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
            spf[i] = i;
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;
        for (int i=3; i*i<MAXN; i++)
        {
            if (spf[i] == i)
            {
                for (int j=i*i; j<MAXN; j+=i)

                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }
    static ArrayList<Integer> getFactorizationUsingSeive(int x) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        while (x != 1) {
            ret.add(spf[x]);
            if (spf[x] != 0) x = x / spf[x];
            else break;
        }
        return ret;
    }
}

class Student12 {
    int  l;long r;
    public Student12(int l, long r) {
        this.l = l;
        this.r = r;
    }

    public String toString()
    {
        return this.l+" ";
    }
}
class Sortbyroll12 implements Comparator<Student12> {

    public int compare(Student12 a, Student12 b){
        return a.l-b.l;
      /*  if(b.r<a.r) return -1;
        else if(b.r==a.r) return 0;
        return 1;*/

        //   return b.r-a.r;
       /*
       if(b.l<a.l) return -1;
       else if(b.l==a.l) {
           return b.r-a.r;
       }
       return 1;*/
        //        return b.r- a.r;
        //        return (int) a.l-(int) b.l;
         /*   if(a.r<b.r) return -1;
            else if(a.r==b.r){
                if(a.r==b.r){
                    return 0;
                }
                if(a.r<b.r) return -1;
                return 1;}
            return 1;  */}
}
