链接：https://codeforces.ml/contest/1360/problem/G

You are given four positive integers nn, mm, aa, bb (1≤b≤n≤501≤b≤n≤50; 1≤a≤m≤501≤a≤m≤50). Find any such rectangular matrix of size n×mn×m that satisfies all of the following conditions:

  • each row of the matrix contains exactly aa ones;
  • each column of the matrix contains exactly bb ones;
  • all other elements are zeros.

If the desired matrix does not exist, indicate this.

For example, for n=3n=3, m=6m=6, a=2a=2, b=1b=1, there exists a matrix satisfying the conditions above:

 

∣∣∣∣010100001010001100∣∣∣∣|010001100100001010|

Input

The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Then tt test cases follow.

Each test case is described by four positive integers nn, mm, aa, bb (1≤b≤n≤501≤b≤n≤50; 1≤a≤m≤501≤a≤m≤50), where nn and mm are the sizes of the matrix, and aa and bb 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×mn×m, print nn rows, each of which consists of mm numbers 00&nbs***bsp;11 describing a row of the matrix. Numbers must be printed without spaces.

Example

input

Copy

5
3 6 2 1
2 2 2 1
2 2 2 2
4 4 2 2
2 1 1 2

output

Copy

YES
010001
100100
001010
NO
YES
11
11
YES
1100
1100
0011
0011
YES
1
1

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
ll n,m,a,b,t,mod=1e9+7;
ll ans[100][100];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>a>>b;
		memset(ans,0,sizeof(ans));
		if(a*n==b*m)
		{
			yes;
			int j=1;
			for(int i=1;i<=n;i++)
			{
				for(int k=1;k<=a;j++,k++)
				{
					if(j>m)
					{
						j=1;
					}
					ans[i][j]=1;
				}
			}
			for(int i=1;i<=n;i++)
			{
				for(j=1;j<=m;j++)
				{
					cout<<ans[i][j];
				}
				cout<<endl;
			} 
		}
		else
		{
			no;
		}
	}
    
}