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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.TreeSet;
public class A { 
	static void merge(int arr[], int l, int m, int r) 
    { 
        int n1 = m - l + 1; 
        int n2 = r - m; 

        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
        int i = 0, j = 0; 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
    static void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    }
    static void revOrder(int[] arr) {
    	int[] a = new int[arr.length];
		for(int i=0;i<arr.length;i++) {
			a[i] = arr[arr.length-i-1];
		}
		for(int i=0;i<arr.length;i++) arr[i] = a[i];
	}
    static int next(int target, ArrayList<Integer> al) {
        int start = 0, end = al.size() - 1;  
        int ans = -1;  
        while (start < end) {  
            int mid = start + (end-start) / 2; 
            if (al.get(mid) <=target) {  
                start = mid + 1;
                ans = mid;
            }   
            else {   
                end = mid - 1;  
            }  
        }  
        return ans;  
    }
    static void pf(int n, ArrayList<Integer> al) 
    {
        for (int i=1; i<=Math.sqrt(n); i++) 
        { 
            if (n%i==0) 
            { 
                if (n/i == i) {
		al.add(i);
		}
       
                else{
		al.add(i);
		al.add(n/i);
		}
            } 
        } 
    }
    static long power(long x, long y, long p) 
    {  
        long res = 1;      
        x = x % p;  
  
       if (x == 0) return 0;    
  
        while (y > 0) 
        {  
            if((y & 1)==1) 
                res = (res * x) % p; 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    } 
    static int gcd(int a, int b) 
    {
        if (a == 0) 
            return b; 
        if (b == 0) 
            return a; 
        int k; 
        for (k = 0; ((a | b) & 1) == 0; ++k)  
        { 
            a >>= 1; 
            b >>= 1; 
        }  
        while ((a & 1) == 0) 
            a >>= 1; 

        do { 
            while ((b & 1) == 0) 
                b >>= 1; 

            if (a > b)  
            {  
                int temp = a; 
                a = b; 
                b = temp; 
            } 
  
            b = (b - a); 
        } while (b != 0); 
        return a << k; 
    }
	static long inv(long a, long m){
     return power(a, m-2, m); 
    } 
	static long ncr(int n, int r, long p) 
    {
        long C[]=new long[r+1]; 
        C[0] = 1; 
        for (int i = 1; i <= n; i++) 
        {
            for (int j = Math.min(i, r); j > 0; j--)  
                C[j] = (C[j] + C[j-1])%p; 
        } 
        return C[r]; 
    } 
    static DecimalFormat df = new DecimalFormat("0.0000000000");
    static PrintWriter out = new PrintWriter(System.out);
	public static void main(String[] args) {
		try {
			BufferInput in = new BufferInput();
			int t = in.nextInt();
			while(t-->0) {
				int n = in.nextInt();
				int m = in.nextInt();
				int a = in.nextInt();
				int b = in.nextInt();		 
		            if (a * n != b * m) {
		                out.println("NO");
		                continue;
		            }
		 
		            int[][] ans = new int[n][m];
		            for (int j = 0, i = 0; j < m; j++) {
		                for (int k = 0; k < b; k++) {
		                    i = (i + 1) % n;
		                    ans[i][j] = 1;
		                }
		            }
		 
		            out.println("YES");
		            for (int i = 0; i < n; i++) {
		                for (int j = 0; j < m; j++)
		                    out.print(ans[i][j]);
		                out.println();
		            }
			}
			out.close();
			
		}catch(Exception e) {}

	}
	
	static class Pair implements Comparable<Pair>
	{
		int x;int y;
		
		Pair(int i,int o)
		{
			x=i;y=o;
		}
		public int compareTo(Pair n)
		{
			if(this.x!=n.x) return this.x-n.x;
			return this.y-n.y;
		}
	}
static class BufferInput {
		
		final private int BUFFER_SIZE = 1 << 16;
		
		private DataInputStream din;
		
		private byte[] buffer;
		
		private int bufferPointer, bytesRead;
		
		public BufferInput() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public BufferInput(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[64];
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}
		
		public String nextString() throws IOException{
			
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			
			StringBuilder builder = new StringBuilder();
			builder.append((char)c);
			c = read();
			while(!Character.isWhitespace(c)){
				builder.append((char)c);
				c = read();
			}
			
			return builder.toString();
		}
		
		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 int[] nextIntArray(int n) throws IOException {
			int arr[] = new int[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextInt();
			}
			return arr;
		}
		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 long[] nextLongArray(int n) throws IOException {
			long arr[] = new long[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public char nextChar() throws IOException{
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			return (char) c;	
		}
		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;
		}
		public double[] nextDoubleArray(int n) throws IOException {
			double arr[] = new double[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextDouble();
			}
			return arr;
		}
		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();
		}
	}
}
