You are given matrix with n rows and n columns filled with zeroes. You should put k ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diagonal that goes from the top left to the bottom right corner) and is lexicographically maximal.

One matrix is lexicographically greater than the other if the first different number in the first different row from the top in the first matrix is greater than the corresponding number in the second one.

If there exists no such matrix then output -1.


-----Input-----

The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 10^6).


-----Output-----

If the answer exists then output resulting matrix. Otherwise output -1.


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

Output
1 0 
0 0 

Input
3 2

Output
1 0 0 
0 1 0 
0 0 0 

Input
2 5

Output
-1

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

def main():
    import sys

    readln = sys.stdin.readline
    try:
        while True:
            n, k = list(map(int, input().split()))
            a = [['0'] * n for i in range(n)]
            i = j = 0
            while k > 0:
                if i == j:
                    a[i][j] = '1'
                    k -= 1
                    j += 1
                elif k >= 2:
                    a[i][j] = a[j][i] = '1'
                    k -= 2
                    j += 1
                elif i != n - 1:
                    a[i + 1][i + 1] = '1'
                    k = 0
                else:
                    assert a[i][i] == '1'
                    a[i][i] = '0'
                    a[i][j] = a[j][i] = '1'
                    k = 0

                if j == n:
                    i += 1
                    if i == n and k > 0:
                        print(-1)
                        break
                    j = i
            else:
                for row in a:
                    print(' '.join(row))

    except EOFError:
        pass

main()


n, k = [int(x) for x in input().split()]

if k > n*n:
    print('-1')
else:


    res = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i > j:
                res[i][j] = res[j][i]
            elif i == j:
                if k > 0:
                    res[i][j] = 1
                    k -= 1
            else:
                if k > 1:
                    res[i][j] = 1
                    k -= 2
    for i in range(n):
        print(' '.join(str(res[i][j]) for j in range(n)))


def main():
    n, k = map(int, input().split())

    if k > n**2:
        print(-1)
        return

    A = [[0] * n for _ in range(n)]

    i = 0
    j = 0
    while k > 1:
        A[i][j] = 1
        k -= 1
        j += 1
        while k > 1 and j < n:
            A[i][j] = 1
            A[j][i] = 1
            j += 1
            k -= 2
        i += 1
        j = i
    if k == 1:
        A[i][j] = 1

    for i in range(n):
        for j in range(n):
            print(A[i][j], end=' ')
        print()


def __starting_point():
    main()

__starting_point()

import sys

def solve():
    n, k = map(int, input().split())

    if k > n**2:
        print(-1)
    else:
        mat = [[0]*n for i in range(n)]

        for i in range(n):
            for j in range(i, n):
                if k <= 0:
                    break
                if i == j:
                    mat[i][i] = 1
                    k -= 1
                else:
                    if k > 1:
                        mat[i][j] = mat[j][i] = 1
                        k -= 2

        for mat_r in mat:
            print(*mat_r)

def __starting_point():
    solve()
__starting_point()

n, k = list(map(int, input().split()))

if n * n < k:
    print(-1)
else:
    arr = [[0 for _ in range(n)] for _ in range(n)]
    cnt = 0
    for i in range(n):
        if cnt < k:
            arr[i][i] = 1
            cnt += 1
        for j in range(i + 1, n):
            if cnt <= k - 2:
                arr[i][j] = 1
                arr[j][i] = 1
                cnt += 2
    for r in arr:
        print(' '.join(map(str, r)))




def main(n, k):
    total = n*n
    if total < k:
        print(-1)
        return

    m = [[0]*n for _ in range(n)]
    fill(m, n, k)
    print_m(m)

def fill(m, n ,k):
    for i in range(n):
        for j in range(i, n):
            if k == 0:
                return

            if i == j:
                m[i][j] = 1
                k -= 1
            elif k == 1:
                m[i+1][i+1] = 1
                k = 0
                return
            else:
                m[i][j] = 1
                m[j][i] = 1
                k -= 2

def print_m(m):
    for row in m:
        print(' '.join(map(str, row)))


n, k = [int(x) for x in input().split()]
main(n, k)



n, k = list(map(int, input().split() ))

if k> n*n:
    print(-1)
else:
    b = [[0]*n for i in range(n)]
    c = 0
    i = 0
    j = 0
    t = -1
    while c < k:
        if i == j:
            b[i][j] = 1
            c += 1
            j += 1
            t = 0
            
        elif j == n:
            i += 1
            j = i
            t = 1
            
        else:
            
            b[i][j] = 1
            b[j][i] = 1
            j += 1
            c+=2
            t = 2
            
    if c == k:
        p = ""
        for q in range(n):
            for w in range(n):
                p += str(b[q][w]) + " "
            print(p)
            p = ""
                
    else:
        if t == 0:
            j -= 1
        if t == 1:
            i -=1
            j = n-1
        if t == 2:
            j -=1
        b[i][j] = 0
        b[j][i] = 0
        b[i+1][i+1] = 1
        p = ""
        for q in range(n):
            for w in range(n):
                p += str(b[q][w]) + " "
            print(p)
            p = ""
    


def maxim():
    n,k=list(map(int,input().strip().split()))
    if k<0:
        print(-1)
        return

    if k>(n**2):
        print(-1)
        return
    
    a=[[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        if k>=1:
            a[i][i]=1
            k-=1
        for j in range(i+1,n):
            if k>=2:
                a[i][j]=1
                a[j][i]=1
                k-=2
            elif k>=1:
                break
    if k>0:
        print(-1)
        return

    for i in range(n):
        b=[str(i) for i in a[i]]
        b=' '.join(b)
        print(b)

maxim()


def show():
    for i in range(n):
        print(' '.join([str(s) for s in a[i]]))

n,k=[int(s) for s in input().split()]
a=[[0 for i in range(n)] for j in range(n)]
if k>n**2:
    print(-1)
elif k==0:
    show()
else:
    for i in range(n):
        if k>0:
            a[i][i]=1
            k-=1
            t=i
            while k>=2 and t<n-1:
                t+=1
                a[i][t]=1
                a[t][i]=1
                k-=2
        else:
            break
    show()

n, k = list(map(int, input().split()))
a = [[0 for j in range(n)]for i in range(n)]
if n * n < k:
    print(-1)
    return
for i in range(n):
    cur = 2 * (n - i) - 1
    if cur <= k:
        k -= cur
        for j in range(i, n):
            a[i][j] = 1
            a[j][i] = 1
    else:
        if k == 0:
            break
        if k == 1:
            a[i][i] = 1
            break
        for j in range(i, i + (k + 1) // 2):
            a[i][j] = 1
            a[j][i] = 1
        if not k % 2:
            a[i + 1][i + 1] = 1
        break
        
for i in a:
    print(*i)
    


#!/usr/bin/env python3
from sys import stdin,stdout

def ri():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()

n, k = ri()

if k > n*n:
    print(-1)
    return

m = [[0 for _ in range(n)] for __ in range(n)]

for i in range(n):
    if k == 1:
        m[i][i] = 1
        k-=1
        break
    if k == 0:
        break
    m[i][i] = 1
    k -= 1
    for j in range(i+1, n):
        if k == 1:
            m[i+1][i+1] = 1
            k -= 1
            break
        if k == 0:
            break
        m[i][j] = 1
        m[j][i] = 1
        k -= 2

for i in range(n):
    print(*m[i])


n, k = map(int, input().split())

mat = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if i == j and k > 0:
            mat[i][j] = 1
            k -= 1
        elif i < j and k > 1:
            mat[i][j] = mat[j][i] = 1
            k -= 2
if k > 0:
    print(-1)
    return

print("\n".join(" ".join(map(str, e)) for e in mat))


s = input()
n = int(s.split(' ')[0])
k = int(s.split(' ')[1])

arr = []
for i in range(n):
    arr.append([0]*n)
if k > n*n:
    print(-1)
else:
    l = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 0:
                if l < k:
                    if i == j:
                        arr[i][j] = 1
                        l += 1
                    elif l < k - 1:
                        arr[i][j] = 1
                        arr[j][i] = 1
                        l += 2

    for i in range(n):
        for j in range(n):
           print(arr[i][j], end=' ')
        print()


import sys

def solve():
    n, k = map(int, input().split())

    mat = [[0]*n for i in range(n)]

    for i in range(n):
        for j in range(i, n):
            if k == 0:
                break
            if i == j:
                mat[i][j] = 1
                k -= 1
            elif k > 1:
                mat[i][j] = mat[j][i] = 1
                k -= 2

    if k != 0:
        print(-1)
        return

    for mat_r in mat:
        print(*mat_r)

def __starting_point():
    solve()
__starting_point()

import sys
import math
n,k = map(int, input().split())
ans = [[0 for i in range(n)] for i in range(n)]
row = 0;
col = 0;
scol = 0;
while(row < n):
    col = scol
    while(col < n):
        if(col == row and k > 0):
            ans[row][col] = 1
            k  -= 1
        elif k > 0:
            if k >= 2:
                ans[row][col] = 1
                ans[col][row] = 1
                k -= 2
        col += 1
     
    row += 1
    scol += 1
if k == 0:
    for i in range(n):
        for j in range(n):
            print(ans[i][j], end = " ")
        print()
else:
    print(-1)


'''input
4 5
'''
n, k = list(map(int, input().split()))
m = [["0"]*n for _ in range(n)] 
for x in range(n):
	for y in range(x, n):
		if x == y and k >= 1:
			m[x][y] = "1"
			k -= 1
		elif k >= 2:
			m[x][y] = "1"
			m[y][x] = "1"
			k -= 2
if k > 0:
	print(-1)
else:
	print("\n".join([" ".join(i) for i in m]))












n,k = list(map(int,input().split()))
ks = k
l = []
for i in range(n):
    p = []
    for j in range(n):
        p.append(0)
    l.append(p)
if(k>n**2):
    print(-1)
else:
    for i in range(n):
        for j in range(n):
            if k==0:
                break
            if(i==j):
                k -=1
                l[i][j] = 1
            else:
                if k>1 and l[j][i]==0:
                    k-=2
                    l[i][j] = 1
                    l[j][i] = 1
    ones = 0
    for row in l:
        ones += row.count(1)
    if ones!=ks:
        print(-1)
    else:
        for i in l:
            s = ""
            for j in i:
                s += " "+str(j)
            print(s[1:])



def main():
    n, k = list(map(int, input().split()))
    l = [['0'] * n for _ in range(n)]
    for y, row in enumerate(l):
        if not k:
            break
        k -= 1
        row[y] = '1'
        for x in range(y + 1, n):
            if k < 2:
                break
            k -= 2
            l[x][y] = row[x] = '1'
    if k:
        print(-1)
    else:
        for row in l:
            print(' '.join(row))


def __starting_point():
    main()

__starting_point()

import math,string,itertools,collections,re,fractions,array,copy
import bisect
import heapq
from itertools import chain, dropwhile, permutations, combinations
from collections import deque, defaultdict, OrderedDict, namedtuple, Counter, ChainMap


# Guide:
#   1. construct complex data types while reading (e.g. graph adj list)
#   2. avoid any non-necessary time/memory usage
#   3. avoid templates and write more from scratch
#   4. switch to "flat" implementations

def VI(): return list(map(int,input().split()))
def I(): return int(input())
def LIST(n,m=None): return [0]*n if m is None else [[0]*m for i in range(n)]
def ELIST(n): return [[] for i in range(n)]
def MI(n=None,m=None): # input matrix of integers
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = VI()
    return arr
def MS(n=None,m=None): # input matrix of strings
    if n is None: n,m = VI()
    arr = LIST(n)
    for i in range(n): arr[i] = input()
    return arr
def MIT(n=None,m=None): # input transposed matrix/array of integers
    if n is None: n,m = VI()
    a = MI(n,m)
    arr = LIST(m,n)
    for i,l in enumerate(a):
        for j,x in enumerate(l):
            arr[j][i] = x
    return arr

def main(info=0):
    n,k = VI()
    if k>n*n:
        print("-1")
    else:
        m = [["0" for _ in range(n)] for _ in range(n)]
        i,j = 0,0
        for i in range(n):
            for j in range(i, n):
                if k==0: break
                if i==j:
                    m[i][j] = "1"
                    k -= 1
                else:
                    if k==1: continue
                    m[i][j] = "1"
                    m[j][i] = "1"
                    k -= 2
            if k==0: break
        for l in m:
            print(" ".join(l))




def __starting_point():
    main()

__starting_point()

def is_available(i, j):
    return i < n and j < n and matrix[i][j] == 0

n, k = list(map(int, input().split()))

if k > n*n:
    print(-1)
else:
    matrix = []
    for i in range(n):
        matrix.append([0] * n)
    if(k%2 == 1):
        matrix[0][0] = 1
        k -= 1

    for i in range(n):
        for j in range(n):
            if k == 0:
                i = n
                break
            if matrix[i][j] == 1:
                continue
            if i == j:
                matrix[i+1][j+1] = matrix[i][j] = 1
            else:
                matrix[i][j] = matrix[j][i] = 1
            k -= 2

    if k >0:    print(-1)
    else:       print('\n'.join([' '.join(map(str, row)) for row in matrix]))


def is_available(i, j):
    return i < n and j < n and matrix[i][j] == 0

n, k = list(map(int, input().split()))

if k > n*n:
    print(-1)
else:
    matrix = []
    for i in range(n):
        matrix.append([0] * n)
    if(k%2 == 1):
        matrix[0][0] = 1
        k -= 1

    for i in range(n):
        for j in range(n):
            if k == 0:
                i = n
                break
            if matrix[i][j] == 1:
                continue
            if i == j:
                matrix[i+1][j+1] = matrix[i][j] = 1
            else:
                matrix[i][j] = matrix[j][i] = 1
            k -= 2

    print('\n'.join([' '.join(map(str, row)) for row in matrix]))


N, K = map( int, input().split() )
if K > N * N:
  exit( print( -1 ) )
G = [ [ 0 for i in range( N ) ] for j in range( N ) ]
for i in range( N ):
  if K == 0: break
  G[ i ][ i ] = 1
  K -= 1
  for j in range( i + 1, N ):
    if K <= 1: break
    G[ i ][ j ], G[ j ][ i ] = 1, 1
    K -= 2
for i in range( N ):
  print( ' '.join( str( v ) for v in G[ i ] ) )


# -*- coding: utf-8 -*-
n,k = list(map(int, input().split(' ')))
if k>n**2:
    print(-1)
elif k==n**2:
    a = [['1']*n for i in range(n)]
    for i in range(n):
        a[i] = ' '.join(a[i])
        print(a[i])
else:
    a = [['0']*n for i in range(n)]
    c = 0
    i = 0
    b = True
    while b and i<n:
        for j in range(n):
            if i==j:
                if c+1>k:
                    continue
                a[i][j] = '1'
                c += 1
            else:
                if a[j][i]!='1':
                    if c + 2 >k:
                        continue
                    a[i][j] = '1'
                    a[j][i] = '1'
                    c += 2
            if c==k:
                b = False
                break
        i += 1
    for i in range(n):
        a[i] = ' '.join(a[i])
        print(a[i])


str_params = input()
params = [int(s) for s in str_params.split(' ')]
n = params[0]
k = params[1]
part = 0;
if (k > n**2):
	print(('%d\n'%(-1)));
else:
	matr = [[0 for x in range(n)] for y in range(n)]
	i = 1
	while part < k:
		matr[i-1][i-1] = 1
		part = part+1
		j = i
		while (k-part>1) & (j<n):
			#print (i-1, j)
			matr[i-1][j] = 1
			matr[j][i-1] = 1
			j = j+1
			part = part+2
		i = i+1;
	for row in matr:
		print(' '.join(map(str,row)))
	print ()


import math
import re



n, k  = list(map(int, input().split()))


if k > n*n:
    print(-1)
    return

a = [[0] * n for i in range(n)]

for i in range(n):
    if k == 0:
        break
    a[i][i] = 1
    k -= 1
    if k == 0:
        break
    elif k == 1:
        a[i+1][i+1] = 1
        break
    else:
        for j in range(i+1, min(n, i + 1 + k//2)):
                       a[i][j] = 1
                       a[j][i] = 1
                       k -= 2


for i in range(n):
    print(' '.join(map(str, a[i])))


# n = int(input())
# a = list(map(int, input().split()))
# #print(' '.join(map(str, a)))
#
#
#
# b = set()
#
# for el in a:
#     if el-1 in b:
#         b.discard(el-1)
#         b.add(el)
#     else:
#         b.add(el)
#
# print(len(b))