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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
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.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    private static FastScanner input;
    private static PrintWriter output;

    public static void main(String[] args) {
//        openFile();
      openConsole();
        int numTest = readInt();
        for (int eachTest = 0; eachTest < numTest; eachTest++) {
            int n = readInt();
            int m = readInt();
            char[][] data = new char[n][m];
            int a = readInt();
            int b = readInt();
            if (a * n != b * m) {
                output.println("NO");
            } else {
                output.println("YES");
                for (int rowId = 0; rowId < n; rowId++) {
                    Arrays.fill(data[rowId], '0');
                    for (int colId = 0; colId < a; colId++) {
                        data[rowId][(colId + a * rowId) % m] = '1';
                    }
                    StringBuilder result = new StringBuilder();
                    for (char elem : data[rowId]) {
                        result.append(elem);
                    }
                    output.println(result.toString());
                }
            }
        }
        closeReader();
    }

    private static Node[] nodes;

    private static void solve(int n, int d) {
        if (minH(n) > d || maxH(n) < d) {
            output.println("NO");
            return;
        }
        output.println("YES");

        StringBuilder sb = new StringBuilder();
        nodes = new Node[n + 1];
        build(1, n, d);
        for (int i = 2; i <= n; i++) {
            sb.append(nodes[i].parent.id).append(' ');
        }
        output.println(sb.toString());
    }

    static class Node {
        int id;
        Node parent;
    }

    public static Node build(int l, int r, int d) {
        if (l > r) {
            return null;
        }

        Node root = new Node();
        root.id = l;
        nodes[root.id] = root;
        d -= (r - l + 1) - 1;

        for (int i = l; i <= r; i++) {
            int left = (i - (l + 1) + 1);
            int right = r - i;

            if (minH(left) + minH(right) <= d && maxH(left) + maxH(right) >= d) {
                int leftAlloc = Math.max(minH(left), d - maxH(right));
                Node leftChild = build(l + 1, i, leftAlloc);
                Node rightChild = build(i + 1, r, d - leftAlloc);

                if (leftChild != null) {
                    leftChild.parent = root;
                }
                if (rightChild != null) {
                    rightChild.parent = root;
                }
                break;
            }
        }
        return root;
    }

    private static int minH(int n) {
        int remaining = n;
        int sum = 0;
        for (int level = 0; remaining > 0; level++) {
            int numNodes = Math.min(remaining, 1 << level);
            remaining -= numNodes;
            sum += numNodes * level;
        }
        return sum;
    }

    private static int maxH(int n) {
        return n * (n - 1) / 2;
    }

    private static void solve_F() {
        int size = readInt();
        List<Pair> data = new ArrayList<>();
        int[] positions = new int[size];
        int[] velocity = new int[size];

        for (int i = 0; i < size; i++) {
            positions[i] = readInt();
        }

        for (int i = 0; i < size; i++) {
            velocity[i] = readInt();
            data.add(new Pair(positions[i], velocity[i]));
        }

        solve(data);
    }

    public static long solve(List<Pair> points) {
        FenwickTree countTree = new FenwickTree(points.size());
        FenwickTree valueTree = new FenwickTree(points.size());

        TreeSet<Integer> velocity = new TreeSet<>();
        for (Pair eachData : points) {
            velocity.add(eachData.velocity);
        }

        TreeMap<Integer, Integer> velocityToIndex = new TreeMap<>();
        for (Integer eachVelocity : velocity) {
            velocityToIndex.put(eachVelocity, velocityToIndex.size() + 1);
        }

        points.sort(Comparator.comparingInt(a -> a.position));

        long sum = 0;
        for (Pair eachPoint : points) {
            int velocityOrder = velocityToIndex.get(eachPoint.velocity);
            if (velocityOrder > 0) {
                long count = countTree.rangeSumQuery(velocityOrder);
                long value = valueTree.rangeSumQuery(velocityOrder);
                sum += eachPoint.position * count - value;
            }
            countTree.addValue(velocityOrder, 1);
            valueTree.addValue(velocityOrder, eachPoint.position);
            System.out.println(sum);
        }
        return sum;
    }

    static class FenwickTree { // one-based DS
        private final int n;
        private final long[] ft;

        private FenwickTree(int size) {
            n = size;
            ft = new long[n + 1];
        }

        // O(log n)
        long rangeSumQuery(int b) {
            long sum = 0;
            while (b > 0) {
                sum += ft[b];
                b -= b & -b;
            } // min?
            return sum;
        }

        long rangeSumQuery(int a, int b) {
            return rangeSumQuery(b) - rangeSumQuery(a - 1);
        }

        // O(log n), update = increment
        void addValue(int k, int val) {
            while (k <= n) {
                ft[k] += val;
                k += k & -k;
            } // min?
        }

        // c * O(log n), c < 1
        long point_query(int idx) {
            long sum = ft[idx];
            if (idx > 0) {
                int z = idx ^ (idx & -idx);
                --idx;
                while (idx != z) {
                    sum -= ft[idx];
                    idx ^= idx & -idx;
                }
            }
            return sum;
        }
    }

    static class Pair {
        int position, velocity;

        public Pair(int aPosition, int aVelocity) {
            position = aPosition;
            velocity = aVelocity;
        }
    }

    private static long readLong() {
        return input.nextLong();
    }

    private static String readString() {
        return input.nextLine();
    }

    private static int readInt() {
        return input.nextInt();
    }

    private static int[] readIntArray(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = readInt();
        }
        return data;
    }

    private static void openConsole() {
        input = new FastScanner(System.in);
        output = new PrintWriter(System.out);
    }

    private static void openFile() {
        ClassLoader classLoader = Main.class.getClassLoader();
        File myFile = new File(classLoader.getResource("input.txt").getFile());
        try {
            input = new FastScanner(new FileInputStream(myFile));
        } catch (FileNotFoundException aE) {
            throw new IllegalStateException("Failed to open input file");
        }
        output = new PrintWriter(System.out);
    }

    private static void closeReader() {
        output.flush();
        output.close();
    }

    private static class FastScanner {
        private StringTokenizer st;
        private final BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        private String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException aE) {
                    throw new IllegalStateException("Failed on tokenizer");
                }
            }
            return st.nextToken();
        }

        boolean hasNext() {
            try {
                return br.ready() || (st != null && st.hasMoreTokens());
            } catch (IOException aE) {
                throw new IllegalStateException("Failed on hasNext()");
            }
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException aE) {
                throw new IllegalStateException("Failed on nextLine()");
            }
        }

        boolean hasNextLine() {
            try {
                return br.ready();
            } catch (IOException aE) {
                throw new IllegalStateException("Failed on hasNextLine()");
            }
        }
    }
}