The farmer decided to build a barn on his farm. But on his farm there are trees and other buildings, which he does not want to remove.   

For simplicity, we represent the farm as a rectangular grid of height $N$ and width ${M}$. Each of the trees and buildings are located in one or more cells of the grid. The barn is a rectangle and should be built on the free cells of the grid.   

Help the farmer to find out how many ways there are to place the barn, for all possible sizes of barns.  

Input Format 

The first line contains two integers $N$ and ${M}$ - the dimensions of the farm. 

The next $N$ lines contains description of the farm: each line contains ${M}$ characters - 0 or 1 (1 means the cell is available/free for building the barn).  

Output Format 

Write $N$ lines with ${M}$ integers in each line. The $j^{th}$ value in the $i^{th}$ line must be equal to the number of ways to place a barn with height ${i}$ and width $j$ in the farm.  

Constraints 

$1\leq N,M\leq1024$  

Sample input  

3 3
011
110
110

Sample Output  

6 3 0
3 1 0
1 0 0

Explanation

Barns with height 1 and width 1:

0*1    01*    011    011    011    011
110    110    *10    1*0    110    110
110    110    110    110    *10    1*0

Barns with height 1 and width 2:

0**    011    011
110    **0    110
110    110    **0

Barns with height 2 and width 1:

0*1    011    011
1*0    *10    1*0
110    *10    1*0

Barns with height 2 and width 2 (there is only one):

011
**0
**0

Barns with height 3 and width 1 (there is only one):

0*1
1*0
1*0

Time Limits: C/C++ 1 sec, Java/C# 2 sec, other languages follow standard TL given in Environment

Difficulty: HARD
Tags: Combinatorics

Starter code:

Solutions:
[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()


[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()


[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()


[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()


[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()


[n, m] = list(map(int, input().split()))
land = []
for i in range(n):
	land.append(list(map(int, list(input()))))
	land[i].append(0)
updist = []
rectrep = []
for i in range(n):
	rectrep.append([0] * m)
for i in range(n):
	updist.append([0] * (m + 1))
	upstack = [[0, -1]]
	for j in range(m + 1):
		if land[i][j]:
			updist[i][j] = updist[i - 1][j] + 1
		nextht = updist[i][j]
		xcoord = j
		while upstack[-1][1] > nextht:
			pair = upstack.pop()
			if upstack[-1][1] > nextht:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				rectrep[upstack[-1][1] - 1][j - pair[0] - 1] -= 1
			else:
				rectrep[pair[1] - 1][j - pair[0] - 1] += 1
				xcoord = pair[0]
				if nextht > 0:
					rectrep[nextht - 1][j - pair[0] - 1] -= 1
		if nextht > upstack[-1][1]:
			upstack.append([xcoord, nextht])
toprint = []
for i in range(n):
	toprint.append([0] * m)
	toprint[i][m - 1] = rectrep[i][m - 1]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + rectrep[i][j]
	for j in range(m - 2, -1, -1):
		toprint[i][j] = toprint[i][j + 1] + toprint[i][j]
for i in range(n - 2, -1, -1):
	for j in range(m):
		toprint[i][j] = toprint[i + 1][j] + toprint[i][j]
for i in range(n):
	for j in range(m):
		print(toprint[i][j], end=' ')
	print()