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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author KIIT
 */
public class ContestDiv3_644 {

    public static void main(String[] args) throws IOException {
        Reader sc = new Reader();
//          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuffer sb  =new StringBuffer();
        while (T-- > 0) {
//            int a = sc.nextInt();
//            int b = sc.nextInt();
//           if(a == b)
//                System.out.println((a+b)*(a+b));
//           else if(2*b<=a || 2*a <=b)
//           {
//               System.out.println(Math.max(a, b)*Math.max(a, b));
//           }
//           else
//           {
//               System.out.println(Math.min(2*a, 2*b)*Math.min(2*a,2* b));
//           }
//              int N = sc.nextInt();
//              int arr[] = new int[N];
//              for(int i =0;i<N;i++)
//                  arr[i] = sc.nextInt();
//              Arrays.sort(arr);
//              int min =  Integer.MAX_VALUE;
//              for(int i = 0;i<N-1;i++)
//              {
//                  if(arr[i+1]-arr[i] < min)
//                  {
//                      min = arr[i+1] - arr[i];
//                  }
//                      
//              }
//              System.out.println(min);
//            int N = sc.nextInt();
//            int arr[] = new int[N];
//            int countEven = 0;
//            int countOdd = 0;
//            Set<Integer> even = new HashSet<>();
//            Set<Integer> odd = new HashSet<>();
//            for (int i = 0; i < N; i++) {
//                arr[i] = sc.nextInt();
//                if(arr[i]%2 == 0){
//                    even.add(arr[i]);
//                    countEven++;
//                }
//                else{
//                    odd.add(arr[i]);
//                    countOdd++;
//                }
//            }
//            if(countEven%2 == 0 && countOdd%2 == 0)
//                System.out.println("YES");
//            else if((countEven%2==0 && countOdd%2!=0) || (countEven%2!=0 && countOdd%2==0) )
//            {
//                System.out.println("NO");   
//            }
//            else 
//            {
//                boolean b = false;
//                for(Integer num : even)
//                {
//                    if(odd.contains(num-1) || odd.contains(num+1))
//                    {
//                        b = true;
//                        break;
//                    }
//                }
//                if(b)
//                    System.out.println("YES");
//                else
//                    System.out.println("NO");
//                    int n = sc.nextInt();
//                    int k = sc.nextInt();
//                    if(n<=k)
//                        System.out.println(1);
//                    else
//                    {
//                        int val = Math.min((int)(Math.sqrt(n)),k);
//                        int i;
//                        int min = Integer.MAX_VALUE;
//                        
//                        for(i = 1;i<=val;i++)
//                        {
//                            if(n%i == 0 )
//                            {
//                               if(n/i <= k)
//                               {
//                                  min = i;
//                                  break;
//                               }
//                               else
//                               {
//                                   min = Math.min(min, n/i);
//                               
//                            }
//                        }
//                        }
//                        System.out.println(min);
//                    }
//            int n = sc.nextInt();
//            char arr[][] = new char[n][n];
//            for (int i = 0; i < n; i++) {
//                String s = sc.readLine();
//                for (int j = 0; j < n; j++) {
//                    arr[i][j] = s.charAt(j);
//                }
//            }
//            int i;
//            a:
//            for (i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (arr[i][j] == '1') {
//                        if (i + 1 != n && j + 1 != n && arr[i + 1][j] != '1' && arr[i][j + 1] != '1') {
//                            break a;
//                        }
//
//                    }
//
//                }
//            }
//            if (i < n) {
//                System.out.println("NO");
//            } else {
//                System.out.println("YES");
//            }
//            int n = sc.nextInt();
//            int m = sc.nextInt();
//            String arr[] = new String[n];
//            sc.nextLine();
//            for (int i = 0; i < n; i++) {
//                arr[i] = sc.nextLine();
//            }
//            boolean ans = false;
//            a:
//            for (char i = 'a'; i <= 'z'; i++) {
//
//                for (int j = 0; j < m; j++) {
//                    char check[] = arr[0].toCharArray();
//                    check[j] = i;
//                    boolean flag = true;
//                    b:
//                    for (int k = 0; k < n; k++) {
//                        int count = 0;
//                        for (int l = 0; l < m; l++) {
//                            if (check[l] != arr[k].charAt(l)) {
//                                count++;
//                            }
//                            if (count > 1) {
//                                flag = false;
//                                break b;
//                            }
//
//                        }
//
//                    }
//                    if (flag) {
//                        ans = true;
//                        System.out.println(check);
//                        break a;
//                    }
//
//                }
//            }
//            if (!ans) {
//                System.out.println(-1);
//            }
            int m = sc.nextInt();
            int n = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            int ans[][] = new int[m][n];
            if (m * a == n * b) {
                sb.append("YES");
                sb.append(System.getProperty("line.separator"));
                int index = 0;
                for(int i = 0;i<m;i++)
                {
                    int count = 0;
                    while(count!=a)
                    {
                        ans[i][index] = 1;
                        index = (index + 1)%n;
                        count++;
                    }
                }
                for(int i = 0;i<m;i++)
                {
                    for(int j = 0;j<n;j++)
                    {
                        sb.append(ans[i][j]);
                    }
                    sb.append(System.getProperty("line.separator"));
                }
               
            } else {
              sb.append("NO");
              sb.append(System.getProperty("line.separator"));
            }
        }
                System.out.print(sb);
    }

    static class Reader {

        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(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[1000000]; // line length 
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        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 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 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;
        }

        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();
        }

    }
}
