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.math.*;
import java.util.*;
public class AByBMatrix {  
	public static void main(String[] args) {  //2D sort too slow
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
/*
*/
		int T = I.nextInt();
		while (T-->0) {
			int N = I.nextInt();
			int M = I.nextInt();
			int A = I.nextInt();
			int B = I.nextInt();
			boolean good=true;
			int tot_inc = N*A+M*B; //Number of increments is simply the product of occurrences
			//in row and column and number of rows and columns
			if (tot_inc%2==1) good=false; //Each 1 contributes to row and column (contribution
			//is a multiple of 2 no matter what)
			else if (tot_inc/2!=N*A||tot_inc/2!=M*B) good=false; //If required amount of 1s is
			//not equal to the given limit
			O.pln(good?"YES":"NO");
			if (good) {
				int[][] ans = new int[N][M];
				int[] cnts = new int[M]; //Number of ones in each column
				//Keep this 1D
				//Then check for number of columns that have 0,1,2,... 1s in their columns 
				//and slot accordingly (sorting disappears)
				//When hit=0, break and move on to next row
				//Then simply print matrix!
				//[count,index] --> SORT
				StringBuilder ret = new StringBuilder();
				for (int c = 0; c < A; c++) {
					ans[0][c]=1; //Fixing top left for convenience
					cnts[c]++;
					ret.append(1);
				}
				for (int i = A; i < M; i++) ret.append(0);
				ret.append("\n");
				for (int r = 1; r < N; r++) { 
					int hit = A;
					for (int num = 0; num<=50; num++) {
						for (int c = 0; c < M; c++) {
							if (cnts[c]==num) {
								ans[r][c]=1;
								cnts[c]++;
								hit--;
								if (hit==0) break;
							}
						}
						if (hit==0) break; //Once all 1s in that row have been slotted
					}
					for (int c = 0; c < M; c++) {
						ret.append(ans[r][c]);
					}
					if (r<N-1) ret.append("\n");
				}
				O.pln(ret); //just print string builder as matrix
			}
		}
	}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x, long y) {return Math.abs(x-y);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}
