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 solution {
    static Reader sc;
    static OutputStream outputStream = System.out;
    static PrintWriter w = new PrintWriter(outputStream);
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        public Reader() throws Exception
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[Integer.MAX_VALUE]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    public  static long minDigit(long n)
    {
        long minDigit=9;
        while(n>0)
        {
            if((n%10)<minDigit)
            {
                minDigit=n%10;
            }
            n/=10;
        }
        return  minDigit;
    }
    public  static long maxDigit(long n)
    {
        long maxDigit=0;
        while(n>0)
        {
            if((n%10)>maxDigit)
            {
                maxDigit=n%10;
            }
            n/=10;
        }
        return  maxDigit;
    }

    public static void solve()throws Exception
    {
        int n=sc.nextInt(),m=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt();
        int[] rowCount = new int[n];
        int[] colCount = new int[m];
        int[][] arr = new int[n][m];
        Arrays.fill(rowCount,a);
        Arrays.fill(colCount,b);
        boolean isPossible=true;
        int j1=0;
        for(int i=0;i<n;i++)
        {
                for (int j = 0; j < m; j++) {
                    j1%=m;
                    if (rowCount[i] > 0 && colCount[j1] > 0) {
                        arr[i][j1] = 1;
                        rowCount[i]--;
                        colCount[j1]--;
                        j1++;
                    } else {
                        arr[i][j1] = 0;
                    }
                }
        }
        for(int i=0;i<n;i++)
        {
            if(rowCount[i]>0)
            {
                isPossible=false;break;
            }
        }
        for(int i=0;i<m;i++)
        {
            if(colCount[i]>0)
            {
                isPossible=false;break;
            }
        }
        if(isPossible)
        {
            w.println("YES");
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    w.print(arr[i][j]);
                }
                w.println();
            }
        }
        else
        {
            w.println("NO");
        }
    }

    public static void main(String args[]) throws Exception
    {
        if(System.getProperty("ONLINE_JUDGE")==null){
            sc=new Reader("/Users/jenardn/IdeaProjects/codeforces/input");
        }
        else {
            sc = new Reader();
        }
        int t= sc.nextInt();
        while(t-->0)
        {
                solve();
        }
        w.close();
    }
}

class Pair implements Comparable<Pair>
{
    int size,first,second;
    Pair(int first,int second)
    {
        this.size = second-first;
        this.first = first;
        this.second = second;
    }
    public int compareTo(Pair other)
    {
        if(this.size>other.size)
            return -1;
        else if(this.size<other.size)
            return 1;
        else
        {
            if(this.first<other.first)
                return -1;
            else if(this.first>other.first)
                return 1;
            return 0;
        }
    }
}