Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $b$. The matrix must be symmetric, and all digits on the main diagonal must be zeroes.

In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices.

The adjacency matrix of an undirected graph is a square matrix of size $n$ consisting only of "0" and "1", where $n$ is the number of vertices of the graph and the $i$-th row and the $i$-th column correspond to the $i$-th vertex of the graph. The cell $(i,j)$ of the adjacency matrix contains $1$ if and only if the $i$-th and $j$-th vertices in the graph are connected by an edge.

A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to $X$ violates this rule.

The complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$.


-----Input-----

In a single line, three numbers are given $n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n)$: is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement. 


-----Output-----

If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes).

Otherwise, on the first line, print "YES"(without quotes). In each of the next $n$ lines, output $n$ digits such that $j$-th digit of $i$-th line must be $1$ if and only if there is an edge between vertices $i$ and $j$ in $G$ (and $0$ otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes. 

If there are several matrices that satisfy the conditions — output any of them.


-----Examples-----
Input
3 1 2

Output
YES
001
001
110

Input
3 3 3

Output
NO

Difficulty: interview

Starter code:

Solutions:
n, a, b = map(int,input().split())
if a>1 and b>1: print("NO"); return
if 2<=n<=3 and a == b == 1: print("NO"); return
print("YES")

if b == 1:
    adj = [[0]*n for i in range(n)]
    conn = n
    for i in range(n):
        if conn == a: break
        adj[i][i+1] = adj[i+1][i] = 1
        conn-= 1
        if conn == a: break
elif a == 1:
    adj = [[1]*n for i in range(n)]
    conn = n
    for i in range(n): adj[i][i] = 0
    for i in range(n):
        if conn == b: break
        adj[i][i+1] = adj[i+1][i] = 0
        conn-= 1
        if conn == b: break

for row in adj:
    print(*row, sep='')


#     Educational Codeforces Round 45 (Rated for Div. 2)
import collections
from functools import cmp_to_key
#key=cmp_to_key(lambda x,y: 1 if x not in y else -1 )

import sys
def getIntList():
    return list(map(int, input().split()))    

 
            
    
n,a,b = getIntList()
a0 = a
b0 = b
if a0>b0:
    a0,b0 = b,a
if n==2 and (a0,b0) == (1,1):
    print('NO')
    return
if n==3 and (a0,b0) == (1,1):
    print('NO')
    return    
if a>1 and b>1:
    print('NO')
    return

mat = [['0' for y in range(n)]for x in range(n)]
mat1 = [['1' for y in range(n)]for x in range(n)]
if b==1:
    for x in range(n-a):
        mat[x][x+1] = '1'
        mat[x+1][x] = '1'
else:
    mat = mat1
    for x in range(n):
        mat[x][x] = '0'
    for x in range(n-b):
        mat[x][x+1] = '0'
        mat[x+1][x] = '0'

print('YES')
for x in range(n):
    print(''.join(mat[x]))


import math;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n, a, b = getIntList();
if a>1 and b>1:
    print('NO');
elif a==b==1 and (n==2 or n==3):
    print('NO');
else:
    c=max(a, b);
    m=[[0]*n for _ in range(n)];
    for i in range(n-c):
        m[i][i+1]=1;
        m[i+1][i]=1;
    if b>1:
        for i in range(n):
            for j in range(n):
                if i!=j:
                    m[i][j]=1-m[i][j];
    print('YES');
    for i in range(n):
        print(''.join(map(str, m[i])));




str=input().split()
n,a,b=[int(str[x]) for x in range(0,3)]
inv=0
if (b!=1):
	t=a
	a=b
	b=t
	inv=1
	
if (b!=1 or n>1 and n<4 and a==1 and b==1):
	print ('NO')
	return

print ('YES')
	
f=[[0]*n for i in range(0,n)]
#print (f)

for i in range(0,n-a):
	f[i][i+1]=f[i+1][i]=1
#f[0][1]=1

#print (f[0][1],f[1][1],f[2][1])

for i in range(0,n):
	cur=[chr(((f[i][j]^inv)&(i!=j))+48) for j in range(0,n)]
	print (''.join(cur))

n, a, b = map(int, input().split())
if a > 1 < b or a * b == 1 and 1 < n < 4:
    print('NO')
else:
    z, o = ('01', '10')[a < b]
    l = [[z] * n for _ in range(n)]
    for i in range(n):
        l[i][i] = '0'
    for i in range(n - a * b):
        l[i][i + 1] = l[i + 1][i] = o
    print('YES')
    print('\n'.join(map(''.join, l)))

n, a, b = map(int, input().split())
z, o = ('01', '10')[a < b]
n *= not (a > 1 < b or 1 < n * a * b < 4)
l = [[z] * n for _ in range(n)]
for i in range(n):
    l[i][i] = '0'
for i in range(n - a * b):
    l[i][i + 1] = l[i + 1][i] = o
print(('YES', 'NO')[not n])
print('\n'.join(map(''.join, l)))

n,a,b=map(int,input().split())
if a>n:
    print('NO')
    return
if b>n:
    print("NO")
    return
if a==1  and b==1:
    if n==2 or n==3:
        print('NO')
        return
if n==1 and a>1 or n==1 and b>1:
    print('NO')
    return
if min(a,b)>1:
    print('NO')
    return 

def check(mat):
    vis=[0]*n 
    cnt=0
    for i in range(n):
        if vis[i]==0:
            q=[i]
            cnt+=1 
            vis[i]=1  
            while q:
                t=q.pop(0)
                for j in range(n):
                    if mat[t][j]==1 and vis[j]==0:
                        vis[j]=1 
                        q.append(j)
        return cnt 
mat=[[0 for i in range(n)] for j in range(n)]
m=max(a,b)
j=1 
for i in range(n):
    if j<n:
        mat[i][j]=1 
        mat[j][i]=1 
    j+=1 
for i in range(m-1):
    curr=n-i-1 
    for j in range(n):
        if mat[curr][j]==1:
            mat[curr][j]=0 
            mat[j][curr]=0 
if b==1:
    print('YES')
    for i in range(n): 
        print(*mat[i],sep='')
    
else:
    print('YES')
    for i in range(n):
        for j in range(n):
            mat[i][j]=1-mat[i][j]
    for i in range(n):
        mat[i][i]=0
    for i in range(n):
        print(*mat[i],sep='')

n, a, b = map(int, input().split())
if (n == 3 or n == 2) and (a == 1 and b == 1):
    print("NO")
    return
g = [[0 for i in range(n)] for j in range(n)]
if a > 1 and b == 1:
    for i in range(n - a - 1, -1, -1):
        g[i][i + 1] = g[i + 1][i] = 1
elif b > 1 and a == 1:
    a, b = b, a
    for i in range(n - a - 1, -1, -1):
        g[i][i + 1] = g[i + 1][i] = 1
    for i in range(n):
        for j in range(n):
            if g[i][j] == 0:
                g[i][j] = 1
            elif g[i][j] == 1:
                g[i][j] = 0
    for i in range(n):
        g[i][i] = 0
elif a == 1 and b == 1:
    for i in range(n - 1):
        g[i][i + 1] = g[i + 1][i] = 1
elif a > 1 and b > 1:
    print("NO")
    return
print("YES")
for i in range(n):
    for j in range(n):
        print(g[i][j], end='')
    print()

n, a, b = list(map(int, input().split()))
z, o = ('01', '10')[a < b]
n *= not (a > 1 < b or 1 < n * a * b < 4)
l = [[z] * n for _ in range(n)]
for i in range(n):
    l[i][i] = '0'
for i in range(n - a * b):
    l[i][i + 1] = l[i + 1][i] = o
print(('YES', 'NO')[not n])
print('\n'.join(map(''.join, l)))