AtCoder Grand Contest 038 - 01 Matrix

We have a square grid with H rows and W columns. Snuke wants to write 0 or 1 in each of the squares. Here, all of the following conditions have to be satisfied:

* For every row, the smaller of the following is A: the number of 0s contained in the row, and the number of 1s contained in the row. (If these two numbers are equal, “the smaller” should be read as “either”.)
* For every column, the smaller of the following is B: the number of 0s contained in the column, and the number of 1s contained in the column.



Determine if these conditions can be satisfied by writing 0 or 1 in each of the squares. If the answer is yes, show one way to fill the squares so that the conditions are satisfied.

Constraints

* 1 \leq H,W \leq 1000
* 0 \leq A
* 2 \times A \leq W
* 0 \leq B
* 2 \times B \leq H
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


H W A B


Output

If the conditions cannot be satisfied by writing 0 or 1 in each of the squares, print -1.

If the conditions can be satisfied, print one way to fill the squares so that the conditions are satisfied, in the following format:


s_{11}s_{12}\cdots s_{1W}
s_{21}s_{22}\cdots s_{2W}
\vdots
s_{H1}s_{H2}\cdots s_{HW}


Here s_{ij} is the digit written in the square at the i-th row from the top and the j-th column from the left in the grid.

If multiple solutions exist, printing any of them will be accepted.

Examples

Input

3 3 1 1


Output

100
010
001


Input

1 5 2 0


Output

01010

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(H, W, A, B) = map(int, input().split())
for i in range(B):
	print('0' * A + '1' * (W - A))
for j in range(H - B):
	print('1' * A + '0' * (W - A))


(H, W, A, B) = map(int, input().split())
ans = [0] * H
for i in range(H):
	if i < B:
		ans[i] = '0' * A + '1' * (W - A)
	else:
		ans[i] = '1' * A + '0' * (W - A)
print('\n'.join(ans))


(H, W, A, B) = map(int, input().split())
for h in range(B):
	print('1' * A + '0' * (W - A))
for h in range(H - B):
	print('0' * A + '1' * (W - A))


(H, W, A, B) = map(int, input().split())
ans = [[1] * A + [0] * (W - A)] * (H - B) + [[0] * A + [1] * (W - A)] * B
print('\n'.join((''.join((str(e) for e in r)) for r in ans)))


(h, w, a, b) = map(int, input().split())
for i in range(b):
	print('1' * a + '0' * (w - a))
for j in range(h - b):
	print('0' * a + '1' * (w - a))


(h, w, a, b) = map(int, input().split())
for i in range(h):
	print('0' * a + '1' * (w - a) if i < b else '1' * a + '0' * (w - a))


(H, W, A, B) = map(int, input().split())
for _ in range(B):
	print(''.join(['0'] * A + ['1'] * (W - A)))
for _ in range(H - B):
	print(''.join(['1'] * A + ['0'] * (W - A)))


(H, W, A, B) = map(int, input().split())
res1 = '1' * A + '0' * (W - A)
res2 = '0' * A + '1' * (W - A)
for i in range(H):
	if i < B:
		print(res1)
	else:
		print(res2)


(H, W, A, B) = map(int, input().split())
ans = [['1' if h < B and w < A or (B <= h and A <= w) else '0' for w in range(W)] for h in range(H)]
for a in ans:
	print(''.join(a))


(H, W, A, B) = map(int, input().split())
x = '1' * (W - A)
y = '0' * (W - A)
x = x.rjust(W, '0')
y = y.rjust(W, '1')
for i in range(B):
	print(x)
for i in range(H - B):
	print(y)


(H, W, A, B) = map(int, input().split())
ans = []
for i in range(B):
	ans.append('1' * A + '0' * (W - A))
for j in range(H - B):
	ans.append('0' * A + '1' * (W - A))
for k in ans:
	print(k)


(H, W, A, B) = map(int, input().split())
X = ''.join(map(str, [1] * A + [0] * (W - A))) + '\n'
Y = ''.join(map(str, [0] * A + [1] * (W - A))) + '\n'
print((X * B + Y * (H - B))[:-1])


(g, r, a, b) = map(int, input().split())
l = [''.join(['0' if retu < a and gyou < b or (retu >= a and gyou >= b) else '1' for retu in range(r)]) for gyou in range(g)]
print(*l, sep='\n')


(h, w, a, b) = map(int, input().split())
s1 = '0' * a + '1' * (w - a)
s2 = '1' * a + '0' * (w - a)
for i in range(b):
	print(s1)
for i in range(h - b):
	print(s2)


(H, W, A, B) = map(int, input().split())
row_str = '0' * A + '1' * (W - A)
inv_row_str = '1' * A + '0' * (W - A)
for i in range(B):
	print(row_str)
for i in range(H - B):
	print(inv_row_str)


(h, w, a, b) = map(int, input().split())
x = '1' * a + '0' * (w - a)
y = '0' * a + '1' * (w - a)
print('\n'.join([x] * b + [y] * (h - b)))


(H, W, A, B) = map(int, input().split())
print(*['1' * A + '0' * (W - A)] * B + ['0' * A + '1' * (W - A)] * (H - B), sep='\n')


(H, W, A, B) = map(int, input().split())
mat = []
for _ in range(B):
	r = '0' * A + '1' * (W - A)
	mat.append(r)
for _ in range(H - B):
	r = '1' * A + '0' * (W - A)
	mat.append(r)
for i in range(H):
	print(mat[i])


(h, w, a, b) = list(map(int, input().split()))
for _ in range(b):
	print('1' * a + '0' * (w - a))
for _ in range(h - b):
	print('0' * a + '1' * (w - a))


(H, W, A, B) = [int(x) for x in input().split()]
M = [[0] * W for _ in range(H)]
for h in range(H):
	if h < B:
		print('1' * A + '0' * (W - A))
	else:
		print('0' * A + '1' * (W - A))


(H, W, A, B) = [int(x) for x in input().split()]
[print(''.join(['0' if j < A else '1' for j in range(W)])) if i < B else print(''.join(['1' if j < A else '0' for j in range(W)])) for i in range(H)]


(H, W, A, B) = map(int, input().split())
line_s = '0' * A + '1' * (W - A)
opps_s = '1' * A + '0' * (W - A)
for _ in range(B):
	print(line_s)
for _ in range(H - B):
	print(opps_s)


(H, W, A, B) = [int(hwab) for hwab in input().split()]
for h in range(H):
	if 0 <= h < B:
		row = '1' * A + '0' * (W - A)
	else:
		row = '0' * A + '1' * (W - A)
	print(row)


(H, W, A, B) = map(int, input().split())
s1 = '0' * A + '1' * (W - A)
s2 = '1' * A + '0' * (W - A)
for i in range(B):
	print(s1)
for i in range(H - B):
	print(s2)


(h, w, a, b) = map(int, input().split())
l = [[0 if i < a else 1 for i in range(w)] if j < b else [0 if i >= a else 1 for i in range(w)] for j in range(h)]
for i in l:
	print(''.join(map(str, i)))


(h, w, a, b) = map(int, input().split())
c = '0' * a + '1' * (w - a)
d = '1' * a + '0' * (w - a)
for _ in range(b):
	print(c)
for _ in range(h - b):
	print(d)


(h, w, a, b) = map(int, input().split())
s = '0' * a + '1' * (w - a)
t = '1' * a + '0' * (w - a)
for _ in range(b):
	print(s)
for _ in range(h - b):
	print(t)


(H, W, A, B) = map(int, input().split())
assert A <= W // 2 and B <= H // 2
for y in range(H):
	print(''.join(('1' if (x < A) ^ (y < B) else '0' for x in range(W))))


(H, W, A, B) = map(int, input().split())
b = 0
for i in range(H):
	if b != B:
		w = ['1'] * A + ['0'] * (W - A)
		b += 1
	else:
		w = ['0'] * A + ['1'] * (W - A)
	print(''.join(w))


(H, W, A, B) = map(int, input().split())
a = '0' * A + '1' * (W - A)
b = '1' * A + '0' * (W - A)
for i in range(B):
	print(a)
for i in range(H - B):
	print(b)


(h, w, a, b) = map(int, input().split())
for i in range(h):
	for j in range(w):
		print(int((j < a) ^ (i < b)), end='')
	print()


(h, w, a, b) = map(int, input().split())
l1 = '1' * a + '0' * (w - a)
l2 = '0' * a + '1' * (w - a)
ans = '\n'.join([l1] * b + [l2] * (h - b))
print(ans)


(h, w, a, b) = (int(i) for i in input().split())
for i in range(b):
	print('0' * a + '1' * (w - a))
for _ in range(h - b):
	print('1' * a + '0' * (w - a))


(H, W, A, B) = map(int, input().split())
S = '0' * A + '1' * (W - A)
S1 = '1' * A + '0' * (W - A)
for i in range(H):
	if i <= B - 1:
		print(S)
	else:
		print(S1)


(h, w, a, b) = [int(x) for x in input().split()]
for i in range(h):
	if i < h - b:
		z = '0' * a
		o = '1' * (w - a)
		print(z + o)
	else:
		z = '0' * (w - a)
		o = '1' * a
		print(o + z)


(H, W, A, B) = map(int, input().split())
if A >= W or B >= H:
	print('No')
else:
	[print(''.join(['0'] * (W - A) + ['1'] * A)) for _ in range(B)]
	[print(''.join(['1'] * (W - A) + ['0'] * A)) for _ in range(H - B)]


(H, W, A, B) = map(int, input().split())
hbar = H - B
wbar = W - A
s = '0' * A + '1' * wbar
sbar = '1' * A + '0' * wbar
for i in range(B):
	print(s)
for i in range(hbar):
	print(sbar)


(h, w, a, b) = map(int, input().split())
r = '1' * a + '0' * (w - a)
rp = '0' * a + '1' * (w - a)
for i in range(b):
	print(r)
for i in range(h - b):
	print(rp)


(a, b, c, d) = map(int, input().split())
for i in range(a):
	if i < d:
		print('1' * c + '0' * (b - c))
	else:
		print('0' * c + '1' * (b - c))


(H, W, A, B) = (int(x) for x in input().split())
for i in range(B):
	print(('1' * (W - A)).zfill(W))
for i in range(H - B):
	print(('1' * A).ljust(W, '0'))


(h, w, a, b) = map(int, input().split())
ans = ''.join(['0'] * a + ['1'] * (w - a))
for i in range(b):
	print(ans)
ans = ''.join(['1'] * a + ['0'] * (w - a))
for i in range(h - b):
	print(ans)


(h, w, a, b) = map(int, input().split())
x = ''
y = ''
for i in range(a):
	x += '1'
	y += '0'
for i in range(w - a):
	x += '0'
	y += '1'
for i in range(b):
	print(x)
for i in range(h - b):
	print(y)


(h, w, a, b) = map(int, input().split())
w -= a
print(*['1' * a + '0' * w] * b + ['0' * a + '1' * w] * (h - b))


(H, W, A, B) = map(int, input().split())
ans = []
for h in range(H):
	if h < B:
		ans.append('0' * A + '1' * (W - A))
	else:
		ans.append('1' * A + '0' * (W - A))
for a in ans:
	print(a)


(h, w, a, b) = map(int, input().split())
ans = [''.join([str(int((j < a) ^ (i < b))) for j in range(w)]) for i in range(h)]
print('\n'.join(ans))


(h, w, a, b) = map(int, input().split())
c = []
for i in range(b):
	c.append('1' * a + '0' * (w - a))
for i in range(h - b):
	c.append('0' * a + '1' * (w - a))
print(*c, sep='\n')


(H, W, A, B) = map(int, input().split())
for H in range(H):
	if H < B:
		line = '0' * A + '1' * (W - A)
	else:
		line = '1' * A + '0' * (W - A)
	print(line)


(H, W, A, B) = map(int, open(0).read().split())
S = [['01'[(i < B) ^ (j < A)] for j in range(W)] for i in range(H)]
print('\n'.join((''.join(s) for s in S)))


(H, W, A, B) = map(int, input().split())
[print(*[int((i < B) ^ (j < A)) for j in range(W)], sep='') for i in range(H)]


(h, w, a, b) = map(int, input().split())
l1 = '0' * a + '1' * (w - a)
l2 = '1' * a + '0' * (w - a)
for i in range(b):
	print('{}'.format(l1))
for i in range(h - b):
	print('{}'.format(l2))


def LI():
	return list(map(int, input().split()))
(H, W, A, B) = LI()
S = '1' * A + '0' * (W - A)
for _ in range(B):
	print(S)
S = '0' * A + '1' * (W - A)
for _ in range(H - B):
	print(S)


(h, w, a, b) = map(int, input().split())
if a > w // 2 or b > h // 2:
	print('No')
else:
	for i in range(h):
		t = i < b
		print(('0' * (w - a) + '1' * a) * (1 - t) + ('1' * (w - a) + '0' * a) * t)


(h, w, a, b) = map(int, input().split())
li1 = str(1) * a + str(0) * (w - a)
li2 = str(0) * a + str(1) * (w - a)
for _ in range(h - b):
	print(li1)
for _ in range(b):
	print(li2)


(H, W, A, B) = map(int, input().split())
t = [[0] * A + [1] * (W - A)] * B + [[1] * A + [0] * (W - A)] * (H - B)
for t_i in t:
	print(*t_i, sep='')


(h, w, a, b) = map(int, input().split())
r1 = '0' * a + '1' * (w - a)
r2 = '1' * a + '0' * (w - a)
for _ in range(b):
	print(r1)
for _ in range(h - b):
	print(r2)


(H, W, A, B) = map(int, input().split())
even = '0' * A + '1' * (W - A)
odd = '1' * A + '0' * (W - A)
for i in range(B):
	print(odd)
	print(even)
for i in range(H - 2 * B):
	print(odd)


(h, w, a, b) = map(int, input().split())
s = [['1'] * a + ['0'] * (w - a) for _ in range(b)] + [['0'] * a + ['1'] * (w - a) for _ in range(h - b)]
for x in s:
	print(''.join(x))


(H, W, A, B) = map(int, input().split())
lst = [[0 if i < A and j < B or (A <= i and B <= j) else 1 for i in range(W)] for j in range(H)]
for i in lst:
	print(*i, sep='')


(H, W, A, B) = map(int, input().split())
for i in range(H):
	(s, t) = (str(int(i < H - B)), str(int(i >= H - B)))
	print(s * (W - A) + t * A)


(H, W, A, B) = map(int, input().split())
S = '0' * A + '1' * (W - A)
T = '1' * A + '0' * (W - A)
for _ in range(B):
	print(S)
for _ in range(H - B):
	print(T)


(h, w, a, b) = map(int, input().split())
print(*['0' * a + '1' * (w - a) for _ in range(b)] + ['1' * a + '0' * (w - a) for _ in range(h - b)], sep='\n')


(h, w, a, b) = map(int, input().split())
x = '01'
for i in range(h):
	print(x[i < b] * a + x[i >= b] * (w - a))


(h, w, a, b) = list(map(int, input().split()))
ans = ''
for i in range(1, h + 1):
	if i <= b:
		s = '1' * a + '0' * (w - a)
	else:
		s = '0' * a + '1' * (w - a)
	ans += s + '\n'
print(ans)


(H, W, A, B) = map(int, input().split())
for i in range(H):
	(z, o) = ('0', '1') if i < B else ('1', '0')
	print(''.join([z] * A + [o] * (W - A)))


(H, W, A, B) = map(int, input().split())
X = ''.join(['0'] * A + ['1'] * (W - A))
Y = ''.join(['1'] * A + ['0'] * (W - A))
for i in range(B):
	print(X)
for i in range(H - B):
	print(Y)


(H, W, A, B) = map(int, input().split())
arow = '1' * A + '0' * (W - A)
brow = '0' * A + '1' * (W - A)
for i in range(1, H + 1):
	if i <= B:
		print(brow)
	else:
		print(arow)


(H, W, a, b) = map(int, input().split())
for i in range(H):
	if i <= b - 1:
		print('1' * a + '0' * (W - a))
	else:
		print('0' * a + '1' * (W - a))


(h, w, a, b) = map(int, input().split())
A = []
for i in range(b):
	A.append(['1'] * a + ['0'] * (w - a))
for i in range(h - b):
	A.append(['0'] * a + ['1'] * (w - a))
for l in A:
	print(''.join(l))


(h, w, a, b) = map(int, input().split())
for i in range(h):
	s = [0] * a + [1] * (w - a)
	t = [1] * a + [0] * (w - a)
	if i < b:
		print(''.join(map(str, s)))
	else:
		print(''.join(map(str, t)))


(h, w, a, b) = map(int, input().split())
for i in range(h):
	print(''.join(map(str, [((i < b) + (j < a)) % 2 for j in range(w)])))


(H, W, A, B) = map(int, input().split())
zero_one = '0' * A + '1' * (W - A)
one_zero = '1' * A + '0' * (W - A)
for _ in range(B):
	print(zero_one)
for _ in range(H - B):
	print(one_zero)


(H, W, A, B) = map(int, input().split())
print(*['1' * A + '0' * (W - A)] * B + ['0' * A + '1' * (W - A)] * (H - B))


(h, w, a, b) = map(int, input().split())
row_0 = '0' * a + '1' * (w - a)
row_1 = '1' * a + '0' * (w - a)
for _ in range(b):
	print(row_0)
for _ in range(h - b):
	print(row_1)


(H, W, A, B) = map(int, input().split())
S01 = '0' * A + '1' * (W - A)
S10 = '1' * A + '0' * (W - A)
for i in range(H):
	if i < B:
		print(S01)
	else:
		print(S10)


(h, w, a, b) = map(int, input().split())
if b > h // 2 or a > w // 2:
	print('No')
	exit(0)
for _ in range(h - b):
	print('0' * (w - a) + '1' * a)
for _ in range(b):
	print('1' * (w - a) + '0' * a)


(h, w, a, b) = map(int, input().split())
result = ['0' * a + '1' * (w - a) for _ in range(b)] + ['1' * a + '0' * (w - a) for _ in range(h - b)]
for r in result:
	print(r)


(H, W, A, B) = map(int, input().split())
w1 = ''.join(['1'] * A + ['0'] * (W - A))
w2 = ''.join(['0'] * A + ['1'] * (W - A))
for i in range(B):
	print(w1)
for i in range(H - B):
	print(w2)