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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;



public class COVID {

	static ArrayList<Integer>[] adjList;






	static int[] fac;
	static int mod=998244353;
	static int pow(int b,long e) {
		int ans=1;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b));
			e>>=1;
			b=(int)((b*1l*b));
		}
		return ans;
	}

	static int powmod(int b,long e, int mod) {
		int ans=1;
		b%=mod;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b)%mod);
			e>>=1;
			b=(int)((b*1l*b)%mod);
		}
		return ans;
	}
	
	static int oneUnqiue(int[] arr) {
		int one=0;int two=0;
		for(int i=0;i<arr.length;i++) {
			two|=(one&arr[i]);
			one^=arr[i];
			int turnOff=~(one&two);
			two&=turnOff;
			one&=turnOff;
			
		}
		return one;
	}
	



public static long check(long a, long k)
{
	if(k==1)return a;
	long tmp=a;
	int min=10;
	int max=-1;
	while(tmp!=0) {
		int dig=(int)(a%10);
		min=Math.min(dig, min);
		max=Math.max(dig, max);
		tmp/=10;
	}
	return check(a+min*max,k-1);
}
ArrayList<Pair> arr;
static int idx;

public static boolean moreThanOne(char[] a, char[] b) {
	int c=0;
	for(int i=0;i<a.length;i++)
		if(a[i]!=b[i]) {
			c++;
			if(c>1)return true;
		}
	return false;
}
static int[][] grid;

static int n,m,a,b;
static int[] col;
public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw =new PrintWriter(System.out);
		int t=sc.nextInt();
		h:while(t-->0) {
			n=sc.nextInt();
			m=sc.nextInt();
			a=sc.nextInt();
			b=sc.nextInt();
			grid=new int[n][m];
			int c=0;
			int r=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<a;j++)
					{
					grid[i][(c+j)%m]=1;
					}
				c+=a;
			}
			col=new int[m];
			boolean no=false;
			for(int i=0;i<n&&!no;i++) {
				int rowC=0;
				
				for(int j=0;j<m;j++) {
					rowC+=grid[i][j];
					col[j]+=grid[i][j];
				}
				if(rowC!=a)
					no=true;
			}
			for(int i=0;i<col.length;i++)
				if(col[i]!=b)no=true;
			if(no) {
				pw.println("NO");
			}else {
				pw.println("YES");
				for(int i=0;i<n;i++) {
					for(int j=0;j<m;j++) {
						pw.print(grid[i][j]);
					}
					pw.println();
				}
			}
		}
		pw.flush();
		pw.close();
	}

static int bs(int[] a, int val) {
	int l=0;
	int h=a.length-1;
	while(l<=h) {
		int mid=(l+h+1)>>1;
		if(a[mid]>=val)
			h=mid-1;
		else
			l=mid+1;
	}
	return h+1;
}


static boolean[] isPrime;
static ArrayList<Integer> primes;
public static void sieve(int N) {// O( n log( log n ) )
	isPrime= new boolean[N+1];//u can save half the memory by neglecting all even numbers since they aren't primes
	primes= new ArrayList<>(N);
	Arrays.fill(isPrime, true);
	isPrime[0]=isPrime[1]=false;
	for(int i=2;i*i<=N;i++) {
		if(isPrime[i]) {
			for(int j=i*i;j<=N;j+=i) {
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=N;i++) {
		if(isPrime[i])primes.add(i);
	}
}

	static long gcd(long a, long b) {
		return (b==0)?a:gcd(b,a%b);
	}
	static long lcm(long a, long b) {
		return a/gcd(a,b)*b;
	}
	public static int log(int n , int base) {
		int ans=0;
		while(n+1>base) {
			ans++;
			n/=base;
		}
		return ans;
	}
	static long square(long l) {
		return l*l;
	}






	static class Pair implements Comparable<Pair>{
		int  x;int y;

		public Pair(int a,int b) {
			this.x=a;y=b;
		}



		public int compareTo(Pair o) {
			return (x==o.x)?((y>o.y)?1:(y==o.y)?0:-1):((x>o.x)?1:-1);
		}


		@Override

		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}



	

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
				arr[i]=nextLong();
			return arr;
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
				arr[i]=nextInt();
			return arr;
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine()," ,");
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}


		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}
