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.util.*;
import java.io.*;
public class g {
	static final FS sc = new FS();
	static final PrintWriter pw = new PrintWriter(System.out);

	static int n, m, a, b;
	public static void main(String[] args) {
		int t = sc.nextInt();
		for(int tt = 1; tt <= t; ++tt) {
			n = sc.nextInt();
			m = sc.nextInt();
			a = sc.nextInt();
			b = sc.nextInt();

			if(n * a == m * b) {
				Dinic dd = new Dinic(n + m);
				for(int i = 0; i < n; ++i) dd.add(dd.s, i, a, 0);
				for(int j = 0; j < m; ++j) dd.add(n + j, dd.t, b, 0);

				for(int i = 0; i < n; ++i) {
					for(int j = 0; j < m; ++j) dd.add(i, n + j, 1, 0);
				}
				
				dd.flow();
				char[][] out = new char[n][m];
				for(char[] z : out) Arrays.fill(z, '0');
				
				for(int i = 0; i < n; ++i) {
					for(Dinic.fedge f : dd.fedges[i]) {
						if(f.flow == 1) out[i][f.v - n] = '1';
					}
				}
				
				pw.println("YES");
				for(int i = 0; i < n; ++i) pw.println(out[i]);
			}
			else pw.println("NO");

		}
		pw.flush();
	}
	static class Dinic {
		final int max = 1_000_000_000;
		int n, s, t;
		ArrayDeque<fedge>[] fedges;
		boolean[] blocked;
		int[] d;
		Dinic(int nn){
			n = nn;
			s = n++;
			t = n++;
			fedges = new ArrayDeque[n];
			for(int i = 0; i < n; ++i) fedges[i] = new ArrayDeque<>();
			blocked = new boolean[n];
			d = new int[n];
		}
		void add(int u, int v, int cap, int flow) {
			fedge ue = new fedge(v, cap, flow);
			fedge ve = new fedge(u, 0, 0);
			ue.rev = ve;
			ve.rev = ue;
			fedges[u].add(ue);
			fedges[v].add(ve);
		}
		int flow() {
			int out = 0;
			while(bfs()) {
				Arrays.fill(blocked, false);
				out += dfs(s, max);
			}
			return out;
		}
		boolean bfs() {
			Arrays.fill(d, -1);
			ArrayDeque<Integer> ad = new ArrayDeque<>();
			d[t] = 0;
			ad.add(t);
			while(!ad.isEmpty()) {
				int curr = ad.poll();
				if(curr == s) return true;
				for(fedge e : fedges[curr]) {
					if(e.rev.cap > e.rev.flow && d[e.v] == -1) {
						d[e.v] = d[curr] + 1;
						ad.add(e.v);
					}
				}
			}
			return false;
		}
		int dfs(int idx, int min) {
			if(idx == t) return min;
			int out = 0;
			for(fedge e : fedges[idx]) {
				if(!blocked[e.v] && d[idx] - 1 == d[e.v] && e.cap - e.flow > 0) {
					int get = dfs(e.v, Math.min(min - out, e.cap - e.flow));
					e.flow += get;
					e.rev.flow = -e.flow;
					out += get;
				}
				if(out == min) return out;
			}
			blocked[idx] = out != min;
			return out;
		}
		static class fedge{
			int v, cap, flow;
			fedge rev;
			fedge(int vv, int cc, int ff){
				v = vv;
				cap = cc;
				flow = ff;
			}
		}
	}
	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}