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
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, m, a, b;
    cin >> n >> m >> a >> b;
    long long int arr[n + 5][m + 5];
    long long int i, j;
    memset(arr, 0, sizeof(arr));
    for (i = 0; i < n; i++) {
      long long int x = a;
      for (j = m - 1; j >= 0; j--) {
        if (x > 0) {
          arr[i][j] = 1;
          x--;
        } else {
          break;
        }
      }
    }
    long long int flag = 0;
    for (j = 0; j < m; j++) {
      long long int count = 0;
      for (i = 0; i < n; i++) {
        if (arr[i][j] == 1) {
          count++;
        }
      }
      if (count > b) {
        flag = 1;
        break;
      }
      long long int y = count;
      while (y < b) {
        for (i = 0; i < n; i++) {
          if (arr[i][j] == 0) {
            for (int h = j + 1; h < m; h++) {
              if (arr[i][h] == 1) {
                arr[i][h] = 0;
                arr[i][j] = 1;
                y++;
                break;
              }
            }
          }
          if (y == b || i == n - 1) {
            break;
          }
        }
        if (y == b || i == n - 1) {
          break;
        }
      }
      if (y != b) {
        flag = 1;
        break;
      }
    }
    if (flag == 1) {
      cout << "NO" << endl;
    } else {
      cout << "YES" << endl;
      for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
          cout << arr[i][j];
        }
        cout << endl;
      }
    }
  }
}
