Alice and Bob play a game. The game consists of several sets, and each set consists of several rounds. Each round is won either by Alice or by Bob, and the set ends when one of the players has won $x$ rounds in a row. For example, if Bob won five rounds in a row and $x = 2$, then two sets ends.

You know that Alice and Bob have already played $n$ rounds, and you know the results of some rounds. For each $x$ from $1$ to $n$, calculate the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $x$ rounds in a row. It is possible that the last set is still not finished — in that case, you should not count it in the answer.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of rounds.

The second line contains one string $s$ of length $n$ — the descriptions of rounds. If the $i$-th element of the string is 0, then Alice won the $i$-th round; if it is 1, then Bob won the $i$-th round, and if it is ?, then you don't know who won the $i$-th round.


-----Output-----

In the only line print $n$ integers. The $i$-th integer should be equal to the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $i$ rounds in a row.


-----Examples-----
Input
6
11?000

Output
6 3 2 1 0 0 

Input
5
01?01

Output
5 1 0 0 0 

Input
12
???1??????1?

Output
12 6 4 3 2 2 1 1 1 1 1 1 



-----Note-----

Let's consider the first test case:

  if $x = 1$ and $s = 110000$ or $s = 111000$ then there are six finished sets;  if $x = 2$ and $s = 110000$ then there are three finished sets;  if $x = 3$ and $s = 111000$ then there are two finished sets;  if $x = 4$ and $s = 110000$ then there is one finished set;  if $x = 5$ then there are no finished sets;  if $x = 6$ then there are no finished sets.

Difficulty: MEDIUM

Starter code:

Solutions:
n = int(input())
s = input()
N = n
N0 = 2 ** (N - 1).bit_length()
data = [n] * (2 * N0)
INF = n

def update(l, r, v):
	L = l + N0
	R = r + N0
	while L < R:
		if R & 1:
			R -= 1
			data[R - 1] = min(v, data[R - 1])
		if L & 1:
			data[L - 1] = min(v, data[L - 1])
			L += 1
		L >>= 1
		R >>= 1

def _query(k):
	k += N0 - 1
	s = INF
	while k >= 0:
		if data[k]:
			s = min(s, data[k])
		k = (k - 1) // 2
	return s

def query(k):
	return _query(k)
alice = [int(s[i] == '0') for i in range(n)]
bob = [int(s[i] == '1') for i in range(n)]
for i in range(1, n):
	alice[i] += alice[i - 1]
	bob[i] += bob[i - 1]
alice.append(0)
bob.append(0)
update_que = [[] for i in range(n)]
alice_win = []
id = 0
while id < n:
	if s[id] != '0':
		pos = id
		while pos < n and s[pos] != '0':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
bob_win = []
id = 0
while id < n:
	if s[id] != '1':
		pos = id
		while pos < n and s[pos] != '1':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
ans = [0] * n
for i in range(n - 1, -1, -1):
	for id in update_que[i]:
		update(0, id + 1, id)
	pos = 0
	res = 0
	while pos < n - i:
		check1 = alice[pos + i] - alice[pos - 1]
		check2 = bob[pos + i] - bob[pos - 1]
		if not check1 or not check2:
			res += 1
			pos += i + 1
		else:
			npos = query(pos)
			if query(pos) == n:
				break
			else:
				pos = npos + i + 1
				res += 1
	ans[i] = res
print(*ans)


import sys
input = sys.stdin.readline
n = int(input())
s = input()
cnt0 = 0
cnt1 = 0
ans = [0] * n
last = [-1] * n
check = [[i + 1] for i in range(n)]
check[0] = []
for i in range(n):
	if s[i] == '1':
		cnt0 = 0
		cnt1 += 1
	elif s[i] == '0':
		cnt0 += 1
		cnt1 = 0
	else:
		cnt0 += 1
		cnt1 += 1
	for j in check[i]:
		if j <= max(cnt0, cnt1) and j <= i - last[j - 1]:
			ans[j - 1] += 1
			last[j - 1] = i
			if i + j < n:
				check[i + j].append(j)
		else:
			pos = i + j - max(cnt0, cnt1)
			if pos < n:
				check[pos].append(j)
ans[0] = n
print(' '.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def RLE(s):
	cc = []
	ww = []
	pc = s[0]
	w = 0
	for c in s:
		if c == pc:
			w += 1
		else:
			cc.append(pc)
			ww.append(w)
			w = 1
			pc = c
	cc.append(pc)
	ww.append(w)
	return (cc, ww)
n = II()
s = SI()
ans = []
(cc, ww) = RLE(s)
if len(cc) == 1 and cc[0] == '?':
	for x in range(1, n + 1):
		ans.append(n // x)
	print(*ans)
	exit()
if cc[0] == '?':
	ww[1] += ww[0]
	ww[0] = 0
if cc[-1] == '?':
	ww[-2] += ww[-1]
	ww[-1] = 0
for i in range(len(cc) - 2):
	if cc[i + 1] == '?' and cc[i] == cc[i + 2]:
		ww[i + 2] += ww[i + 1] + ww[i]
		ww[i + 1] = ww[i] = 0
aa = []
for (c, w) in zip(cc, ww):
	if w == 0:
		continue
	if len(aa) & 1 and c != '?':
		aa.append(0)
	aa.append(w)
aa.append(0)
ans.append(n)
for x in range(2, n + 1):
	bb = []
	r = 0
	pq = 0
	move = 0
	cur = 0
	for i in range(0, len(aa), 2):
		a = aa[i]
		q = aa[i + 1]
		cur += (r + a + q) // x
		r = min(q, (r + a + q) % x)
		if min(x, pq) + a + move + q <= x:
			if bb:
				b = bb.pop()
				bb[-1] += b
				bb.append(0)
			pq = 0
			move = q
		else:
			bb += [move + a, q]
			move = 0
			pq = q
	aa = bb
	ans.append(cur)
	if cur == 0:
		break
ans += [0] * (n - len(ans))
print(*ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
n = val()
s = st()
pref0 = [0]
pref1 = [0]
for i in s:
	if i == '1':
		pref1.append(pref1[-1] + 1)
		pref0.append(pref0[-1])
	elif i == '0':
		pref0.append(pref0[-1] + 1)
		pref1.append(pref1[-1])
	else:
		pref1.append(pref1[-1] + 1)
		pref0.append(pref0[-1] + 1)
next0 = [-1]
next1 = [-1]
m1 = m2 = -1
for i in range(n):
	if s[i] == '1':
		m2 = i
	if s[i] == '0':
		m1 = i
	next0.append(m1)
	next1.append(m2)
flag = 0
last = float('inf')
for x in range(1, n + 1):
	if flag:
		ans = 0
	else:
		ans = start = 0
		while start + x <= n and ans < last:
			if pref0[start + x] - pref0[start] == x:
				start += x
				ans += 1
			elif pref1[start + x] - pref1[start] == x:
				start += x
				ans += 1
			else:
				start = next0[start + x] if next1[start + x] > next0[start + x] else next1[start + x]
				start += 1
	if not ans:
		flag = 1
	last = ans
	print(ans, end=' ')


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop, heapify
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
from itertools import accumulate
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
s = st()
pref0 = [0]
pref1 = [0]
for i in s:
	if i == '1':
		pref1.append(pref1[-1] + 1)
		pref0.append(pref0[-1])
	elif i == '0':
		pref0.append(pref0[-1] + 1)
		pref1.append(pref1[-1])
	else:
		pref1.append(pref1[-1] + 1)
		pref0.append(pref0[-1] + 1)
next0 = [-1]
next1 = [-1]
m1 = m2 = -1
for i in range(n):
	if s[i] == '1':
		m2 = i
	if s[i] == '0':
		m1 = i
	next0.append(m1)
	next1.append(m2)
flag = 0
last = float('inf')
for x in range(1, n + 1):
	if flag:
		ans = 0
	else:
		ans = start = 0
		while start + x <= n:
			if pref0[start + x] - pref0[start] == x:
				start += x
				ans += 1
			elif pref1[start + x] - pref1[start] == x:
				start += x
				ans += 1
			else:
				start = next0[start + x] if next1[start + x] > next0[start + x] else next1[start + x]
				start += 1
	if not ans:
		flag = 1
	print(ans, end=' ')


class BalancingTree:

	def __init__(self, n):
		self.N = n
		self.root = self.node(1 << n, 1 << n)

	def append(self, v):
		v += 1
		nd = self.root
		while True:
			if v == nd.value:
				return 0
			else:
				(mi, ma) = (min(v, nd.value), max(v, nd.value))
				if mi < nd.pivot:
					nd.value = ma
					if nd.left:
						nd = nd.left
						v = mi
					else:
						p = nd.pivot
						nd.left = self.node(mi, p - (p & -p) // 2)
						break
				else:
					nd.value = mi
					if nd.right:
						nd = nd.right
						v = ma
					else:
						p = nd.pivot
						nd.right = self.node(ma, p + (p & -p) // 2)
						break

	def leftmost(self, nd):
		if nd.left:
			return self.leftmost(nd.left)
		return nd

	def rightmost(self, nd):
		if nd.right:
			return self.rightmost(nd.right)
		return nd

	def find_l(self, v):
		v += 1
		nd = self.root
		prev = 0
		if nd.value < v:
			prev = nd.value
		while True:
			if v <= nd.value:
				if nd.left:
					nd = nd.left
				else:
					return prev - 1
			else:
				prev = nd.value
				if nd.right:
					nd = nd.right
				else:
					return prev - 1

	def find_r(self, v):
		v += 1
		nd = self.root
		prev = 0
		if nd.value > v:
			prev = nd.value
		while True:
			if v < nd.value:
				prev = nd.value
				if nd.left:
					nd = nd.left
				else:
					return prev - 1
			elif nd.right:
				nd = nd.right
			else:
				return prev - 1

	@property
	def max(self):
		return self.find_l((1 << self.N) - 1)

	@property
	def min(self):
		return self.find_r(-1)

	def delete(self, v, nd=None, prev=None):
		v += 1
		if not nd:
			nd = self.root
		if not prev:
			prev = nd
		while v != nd.value:
			prev = nd
			if v <= nd.value:
				if nd.left:
					nd = nd.left
				else:
					return
			elif nd.right:
				nd = nd.right
			else:
				return
		if not nd.left and (not nd.right):
			if nd.value < prev.value:
				prev.left = None
			else:
				prev.right = None
		elif not nd.left:
			if nd.value < prev.value:
				prev.left = nd.right
			else:
				prev.right = nd.right
		elif not nd.right:
			if nd.value < prev.value:
				prev.left = nd.left
			else:
				prev.right = nd.left
		else:
			nd.value = self.leftmost(nd.right).value
			self.delete(nd.value - 1, nd.right, nd)

	def __contains__(self, v: int) -> bool:
		return self.find_r(v - 1) == v

	class node:

		def __init__(self, v, p):
			self.value = v
			self.pivot = p
			self.left = None
			self.right = None
n = int(input())
s = input()
alice = [int(s[i] == '0') for i in range(n)]
bob = [int(s[i] == '1') for i in range(n)]
for i in range(1, n):
	alice[i] += alice[i - 1]
	bob[i] += bob[i - 1]
alice.append(0)
bob.append(0)
update_que = [[] for i in range(n)]
alice_win = []
id = 0
while id < n:
	if s[id] != '0':
		pos = id
		while pos < n and s[pos] != '0':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
bob_win = []
id = 0
while id < n:
	if s[id] != '1':
		pos = id
		while pos < n and s[pos] != '1':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
bst = BalancingTree(20)
bst.append(n)
ans = [0] * n
for i in range(n - 1, -1, -1):
	for id in update_que[i]:
		bst.append(id)
	pos = 0
	res = 0
	while pos < n - i:
		check1 = alice[pos + i] - alice[pos - 1]
		check2 = bob[pos + i] - bob[pos - 1]
		if not check1 or not check2:
			res += 1
			pos += i + 1
		else:
			npos = bst.find_r(pos - 1)
			if npos == n:
				break
			else:
				pos = npos + i + 1
				res += 1
	ans[i] = res
print(*ans)


class bitset:

	def __init__(self, n):
		self.size = 1 << (n + 2).bit_length()
		self.bit = [0] * (self.size + 1)

	def append(self, val):
		val += 1
		id = val
		while id <= self.size:
			self.bit[id] += 1
			id += id & -id

	def erase(self, val):
		val += 1
		id = val
		while id <= self.size:
			self.bit[id] -= 1
			id += id & -id

	def cnt(self, val):
		res_sum = 0
		val += 1
		while val > 0:
			res_sum += self.bit[val]
			val -= val & -val
		return res_sum

	def next(self, val):
		val += 1
		base = self.cnt(val - 1)
		start = 0
		end = self.size
		while end - start > 1:
			test = (end + start) // 2
			if self.bit[test] > base:
				end = test
			else:
				start = test
				base -= self.bit[test]
		return end - 1
n = int(input())
s = input()
alice = [int(s[i] == '0') for i in range(n)]
bob = [int(s[i] == '1') for i in range(n)]
for i in range(1, n):
	alice[i] += alice[i - 1]
	bob[i] += bob[i - 1]
alice.append(0)
bob.append(0)
update_que = [[] for i in range(n)]
alice_win = []
id = 0
while id < n:
	if s[id] != '0':
		pos = id
		while pos < n and s[pos] != '0':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
bob_win = []
id = 0
while id < n:
	if s[id] != '1':
		pos = id
		while pos < n and s[pos] != '1':
			pos += 1
		update_que[pos - id - 1].append(id)
		id = pos
	else:
		id += 1
bst = bitset(n)
bst.append(n)
ans = [0] * n
for i in range(n - 1, -1, -1):
	for id in update_que[i]:
		bst.append(id)
	pos = 0
	res = 0
	while pos < n - i:
		check1 = alice[pos + i] - alice[pos - 1]
		check2 = bob[pos + i] - bob[pos - 1]
		if not check1 or not check2:
			res += 1
			pos += i + 1
		else:
			npos = bst.next(pos)
			if npos == n:
				break
			else:
				pos = npos + i + 1
				res += 1
	ans[i] = res
print(*ans)