There are $n$ groups of friends, and each group is numbered from 1 to $n$. The ${i}^{th}$ group contains $a_i$ people. 

They live near a bus stop, and only a single bus operates on this route. An empty bus arrives at the bus stop and all the groups want to travel by the bus. 

However,  group of friends do not want to get separated. So they enter the bus only if the bus can carry the entire group. 

Moreover, the groups do not want to change their relative positioning while travelling.  In other words, group 3 cannot travel by bus, unless group 1 and group 2 have either (a) already traveled by the bus in the previous trip or (b) they are also sitting inside the bus at present.

You are given that a bus of size $\boldsymbol{x}$ can carry $\boldsymbol{x}$ people simultaneously. 

Find the size $\boldsymbol{x}$ of the bus so that 
(1) the bus can transport all the groups and 
(2) every time when the bus starts from the bus station, there is no empty space in the bus (i.e. the total number of people present inside the bus is equal to $\boldsymbol{x}$)?

Input Format 

The first line contains an integer $n$ $(1\leq n\leq10^5)$. The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq10^4)$.

Output Format

Print all possible sizes of the bus in an increasing order.

Sample Input

8
1 2 1 1 1 2 1 3

Sample Output

3 4 6 12

Sample Explanation

In the above example, 
$a_1$ = 1, $a_2$ = 2, $a_3$ = 1, $a_{4}$ = 1, $a_{5}$ = 1, $a_{6}$ = 2, $a_{7}$ = 1, $a_{8}$ = 3.

If x = 1 : 
In the first trip, $a_1$ go by the bus.
There will be no second trip because the bus cannot accommodate group 2. Hence "x = 1" is not the required answer.

If x = 2 :
No bus trip is possible. That's because $a_1$ cannot go alone, as one seat will be left vacant in the bus. And, $a_1$ & $a_2$ cannot go together, because the bus is cannot accommodate both the groups simultaneously.

If x = 3 : 
In the first trip, $a_1$ & $a_2$ go by the bus. 
In the second trip, $a_3$, $a_{4}$ & $a_{5}$ go by the bus. 
In the third trip, $a_{6}$ & $a_{7}$ go by the bus. 
In the fourth trip, $a_{8}$ go by the bus. 

If x = 4 : 
In the first trip, $a_1$, $a_2$ & $a_3$ go by the bus. 
In the second trip,  $a_{4}$, $a_{5}$ & $a_{6}$go by the bus. 
In the third trip, $a_{7}$ & $a_{8}$ go by the bus. 

Similarly you can figure out the output for x= 5, 6 & 7.

Source: hackerrank | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
from math import floor, sqrt, ceil
N = int(input())
groupSize = [int(i) for i in input().split()]
response = list()

def minAndMax(array):
	(minimum, maximum) = (array[0], array[0])
	for el in array[1:]:
		maximum += el
		if el > minimum:
			minimum = el
	return (minimum, maximum)

def multipleOf(begin, n):
	multiples = list()
	res = set((x for tup in ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0) for x in tup if x >= begin))
	res = list(res)
	res.sort()
	return res
(minimum, maximum) = minAndMax(groupSize)
possiblesValues = multipleOf(minimum, maximum)
countPossiblesValues = len(possiblesValues)
nbGroup = len(groupSize)
count = [0] * countPossiblesValues
for el in groupSize:
	for i in range(countPossiblesValues):
		count[i] += el
		if count[i] == possiblesValues[i]:
			count[i] = 0
for i in range(countPossiblesValues):
	if count[i] == 0:
		print(str(possiblesValues[i]), end=' ')


from functools import reduce
from collections import deque

def fill_bus(groups):
	cumulate = [groups[0]]
	for i in range(1, len(groups)):
		cumulate.append(cumulate[i - 1] + groups[i])
	sizes = []
	for bus_size in factors(sum(groups)):
		breaks = list(filter(lambda x: x % bus_size == 0, cumulate))
		idx = 1
		flag = True
		for point in breaks:
			if point != bus_size * idx:
				flag = False
				break
			idx += 1
		if flag:
			sizes.append(bus_size)
	print(''.join((str(i) + ' ' for i in sizes)))

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))))
n = int(input())
groups = list(map(int, input().split()))
max_size = max(groups)
total = sum(groups)
fill_bus(groups)


from math import sqrt

def is_solution(f):
	bus_total = 0
	for g in ar:
		if bus_total + g > f:
			return False
		bus_total += g
		if bus_total == f:
			bus_total = 0
	return True

def factorize(n):
	factors = []
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			factors.append(i)
	return factors
n = int(input())
ar = list(map(int, input().split()))
total = sum(ar)
factors = []
for f in factorize(total):
	if is_solution(f):
		factors.append(f)
	temp = total // f
	if temp != f and is_solution(temp):
		factors.append(temp)
print(' '.join((str(f) for f in sorted(factors))))


from collections import defaultdict
from functools import reduce
input()
data = list(map(int, input().split()))
sums = []
curr = 0
max_elem = 0
for x in data:
	curr += x
	sums.append(curr)
	if x > max_elem:
		max_elem = x
s = frozenset(sums)

def check_division(size):
	curr_size = size
	while curr_size <= curr:
		if curr_size not in s:
			return False
		curr_size += size
	else:
		return curr + size == curr_size
used = set()
res = []
for i in range(1, int(curr ** 0.5) + 1):
	if curr % i == 0:
		b = curr / i
		if i not in used and check_division(i):
			used.add(i)
			res.append(i)
		if b not in used and check_division(b):
			used.add(b)
			res.append(b)
print(' '.join(map(lambda x: str(int(x)), sorted(res))))


from itertools import accumulate as acc
n = int(input())
a = list(acc(map(int, input().split())))
m = a[-1]
s = set(a)
for e in a:
	if m % e != 0:
		continue
	for n in range(2 * e, m, e):
		if n not in s:
			break
	else:
		print(e, end=' ')


import bisect
input()
a = list(map(int, input().split()))
n = len(a)
cumsum = [a[0]]
for i in range(1, n):
	cumsum.append(cumsum[-1] + a[i])
r = []
for i in range(n):
	x = cumsum[i]
	curgrp = i + 1
	while curgrp < n:
		nextsum = cumsum[curgrp - 1] + x
		idx = bisect.bisect(cumsum, nextsum)
		if cumsum[idx - 1] < nextsum:
			break
		curgrp = idx
	else:
		r.append(x)
print(*r)


import math

def check(i, groups):
	rem = i
	for group in groups:
		if group > rem:
			return False
		elif group == rem:
			rem = i
		else:
			rem -= group
	return True
input()
groups = [int(x) for x in input().split(' ')]
total_passengers = sum(groups)
xs = []
i = 1
while i * i <= total_passengers:
	if total_passengers % i == 0:
		if check(i, groups):
			xs.append(i)
		other = total_passengers // i
		if other != i and check(other, groups):
			xs.append(other)
	i += 1
print(' '.join((str(x) for x in sorted(xs))))


n = int(input())
a_i = [int(x) for x in input().split()]
total_people = sum(a_i)
out = []
bus_size = 0
for on_first_bus_cur in range(n):
	bus_size += a_i[on_first_bus_cur]
	if total_people % bus_size != 0:
		continue
	left = on_first_bus_cur + 1
	fail = False
	while left < n:
		on_bus = 0
		for cur in range(left, n):
			on_bus += a_i[cur]
			if on_bus > bus_size:
				fail = True
				break
			elif on_bus == bus_size:
				break
		if on_bus != bus_size:
			fail = True
		if fail:
			break
		left = cur + 1
	if not fail:
		out.append(bus_size)
print(' '.join([str(x) for x in out]))


from math import floor

def isSustainable(size, A):
	sumOfSizes = 0
	for a in A:
		sumOfSizes += a
		if sumOfSizes == size:
			sumOfSizes = 0
		elif size < sumOfSizes:
			return False
	return sumOfSizes == 0
n = int(input())
A = [int(s) for s in input().split()]
busSizes = []
maxSize = sum(A)
size = 1
while size * size <= maxSize:
	if maxSize % size == 0:
		if isSustainable(size, A):
			busSizes.append(size)
		maxSizeDivSize = floor(maxSize / size)
		if maxSizeDivSize != size and isSustainable(maxSizeDivSize, A):
			busSizes.append(maxSizeDivSize)
	size += 1
busSizes.sort()
print(' '.join(map(str, busSizes)))


def factor(n):
	(a, r) = (1, [1])
	while a * a < n:
		a += 1
		if n % a:
			continue
		(b, f) = (1, [])
		while n % a == 0:
			n //= a
			b *= a
			f += [i * b for i in r]
		r += f
	if n > 1:
		r += [i * n for i in r]
	return r
N = int(input())
A = list(map(int, input().split()))
sizes = []
for size in sorted(factor(sum(A))):
	cur = 0
	works = True
	for i in A:
		cur += i
		if cur == size:
			cur = 0
		elif cur > size:
			works = False
			break
	if works:
		sizes.append(size)
print(' '.join(map(str, sizes)))


n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for x in a[1:]:
	b.append(b[-1] + x)
b = set(b)
total = sum(a)
ans = []
for x in b:
	if total % x != 0:
		continue
	y = 2
	while y * x < total:
		if y * x not in b:
			break
		y += 1
	if y * x == total:
		ans.append(x)
ans.append(total)
print(' '.join(map(str, sorted(ans))))


def f(A):
	dp = {}
	s = A[0]
	dp[s] = 1
	for i in range(1, len(A)):
		s += A[i]
		dp[s] = 1
	ts = s
	s = A[0]
	l = []
	for i in range(1, len(A)):
		if ts % s == 0:
			for j in range(2 * s, ts, s):
				try:
					dp[j]
				except:
					break
			else:
				l.append(s)
		s += A[i]
	l.append(ts)
	print(*l)
input()
f([int(i) for i in input().split()])


from collections import deque
import math

def stuff_passengers(size, groups):
	tmp_groups = deque(groups)
	current_capacity = 0
	while len(tmp_groups) > 0:
		if current_capacity > size:
			return False
		current_capacity += tmp_groups.popleft()
		if current_capacity == size:
			current_capacity = 0
	if current_capacity == 0:
		return True

def main():
	num_groups = int(input())
	groups = input()
	groups = groups.split(' ')
	groups = list(map(int, groups))
	max_group = max(groups)
	group_sum = sum(groups)
	solution_set = []
	divisors = set()
	i = 1
	while i <= math.sqrt(group_sum):
		if group_sum % i == 0:
			divisors.add(i)
			divisors.add(int(group_sum / i))
		i += 1
	divisors = filter(lambda x: x >= max_group, divisors)
	for size in divisors:
		if stuff_passengers(size, groups):
			solution_set.append(size)
	solution_set = sorted(solution_set)
	for s in solution_set:
		print(s, end=' ')
main()


__author__ = 'danielbaeck'
import math
n = int(input())
g = [int(i) for i in input().split()]
pos = []

def divs(r):
	d = []
	for i in range(1, math.ceil(math.sqrt(r)) + 1):
		if r % i == 0:
			d.append(i)
			if r / i != i:
				d.append(r / i)
	d = list(set(d))
	return sorted([int(i) for i in d])
for x in divs(sum(g)):
	canTravel = True
	full = 0
	for i in g:
		full += i
		if full > x:
			canTravel = False
			break
		if full == x:
			full = 0
	if canTravel and full == 0:
		pos.append(x)
print(' '.join([str(i) for i in pos]))


def get_all_inf(n):
	res = []
	cur_count = 0
	while n % 2 == 0 and n > 1:
		cur_count += 1
		n //= 2
	if cur_count > 0:
		res.append((2, cur_count))
	i = 3
	while i * i <= n:
		cur_count = 0
		while n % i == 0 and n > 1:
			cur_count += 1
			n //= i
		if cur_count > 0:
			res.append((i, cur_count))
		i += 2
	if n > 1:
		res.append((n, 1))
	return res

def get_factors(n):
	inf = get_all_inf(n)
	inf_len = len(inf)
	ans = []
	stack = []
	stack.append((1, 0))
	while len(stack) > 0:
		(res, pos) = stack.pop()
		if pos == inf_len:
			ans.append(res)
			continue
		(cur, count) = inf[pos]
		st = 1
		for i in range(count + 1):
			stack.append((res * st, pos + 1))
			st *= cur
	return ans
n = int(input())
a = [int(item) for item in input().strip().split()]
sum_a = []
max_a = 0
s = 0
for i in a:
	s += i
	if i > max_a:
		max_a = i
	sum_a.append(s)
res_sum = sum_a[-1]
for x in sorted(get_factors(res_sum)):
	if max_a > x:
		continue
	number_of_interval = res_sum // x
	a = 0
	flag = True
	for i in range(1, number_of_interval):
		b = n
		while b - a > 1:
			c = (a + b) // 2
			if sum_a[c] <= x * i:
				a = c
			else:
				b = c
		if sum_a[a] != x * i:
			flag = False
			break
	if flag:
		print(x, end=' ')


from math import sqrt, floor
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
sq = floor(sqrt(s))
ind = 0
ans1 = []
ans2 = []
for i in range(1, sq + 1):
	if s % i == 0:
		trip = 0
		for ai in a:
			trip += ai
			if trip == i:
				trip = 0
			elif trip > i:
				break
		else:
			ans1.append(i)
		trip = 0
		r = s // i
		if r != i:
			for ai in a:
				trip += ai
				if trip == r:
					trip = 0
				elif trip > r:
					break
			else:
				ans2.insert(0, r)
print(*ans1 + ans2)


def check(arr, size):
	cap = size
	for v in arr:
		cap -= v
		if cap < 0:
			return False
		elif cap == 0:
			cap = size
	return True
T = int(input().strip())
arr = [int(i) for i in input().strip().split()]
candidata = [arr[0]]
result = []
for i in range(1, T):
	candidata.append(candidata[i - 1] + arr[i])
sum = candidata[-1]
for v in candidata:
	if sum % v == 0 and check(arr, v):
		result.append(v)
print(' '.join(map(str, result)))


def bus_sizes(a):
	buses = []
	total = sum(a)
	running = a[0]
	sums = set()
	sums.add((0, running))
	for i in range(1, len(a)):
		running += a[i]
		if total % running == 0:
			sums.add((i, running))
	for s in sums:
		next_sum = 0
		for i in range(s[0] + 1, len(a)):
			next_sum += a[i]
			if next_sum == s[1]:
				next_sum = 0
		if next_sum == 0:
			buses.append(s[1])
	buses.sort()
	return buses
input()
a = list(map(int, input().strip().split()))
print(' '.join(map(str, bus_sizes(a))))


N = int(input())
k = input().split()
total = 0
for i in range(0, len(k)):
	k[i] = int(k[i])
	total = total + k[i]
sum = 0
output = []
for i in range(0, N - 1):
	sum = sum + k[i]
	cursum = sum
	flag = 1
	if (total - sum) % sum != 0:
		continue
	for j in range(i + 1, N):
		cursum = cursum - k[j]
		if cursum < 0:
			flag = 1
			break
		elif cursum == 0:
			flag = 0
			cursum = sum
		else:
			flag = 1
	if flag == 0:
		output.append(sum)
output.append(sum + k[N - 1])
for ele in output:
	print(ele, end=' ')


import sys
lines = [[int(val) for val in line.split()] for line in sys.stdin]
([n], grps) = lines
maxval = grps[0]
poss = []
final = []
sm = 0
for grp in grps:
	if maxval < grp:
		maxval = grp
	sm = sm + grp
	poss.append(sm)
for val in poss:
	if poss[n - 1] % val == 0 and val >= maxval:
		final.append(val)
for val in final.copy():
	temp = val
	for grp in grps:
		temp = temp - grp
		if temp < 0:
			try:
				final.remove(val)
			except:
				pass
			break
		elif temp == 0:
			temp = val
	else:
		if temp != val:
			try:
				final.remove(val)
			except:
				pass
print(' '.join(map(str, final)))


length = int(input())
friends = [int(i) for i in input().split()]
min_bus = max(friends)
bus_size = 0
friend_sum = sum(friends)
for index in range(len(friends)):
	bus_size += friends[index]
	if bus_size >= min_bus and friend_sum % bus_size == 0:
		bus_temp = bus_size
		friend_temp = friend_sum
		test_index = index + 1
		failed = 0
		while test_index < length:
			while bus_temp > 0 and test_index < length:
				bus_temp -= friends[test_index]
				test_index += 1
			if bus_temp != 0:
				failed = 1
				break
			else:
				bus_temp = bus_size
		if not failed:
			print(bus_size, end=' ')
print()


N = int(input())
A = [int(_) for _ in input().split()]
S = sum(A)
Ds = []
for d in range(1, int(S ** 0.5) + 1):
	if S % d == 0:
		Ds.append(d)
		Ds.append(S // d)
Xs = sorted(set(Ds))
sol = []
for x in Xs:
	(s, valid) = (0, True)
	for a in A:
		s += a
		if s > x:
			valid = False
			break
		if s == x:
			s = 0
	if valid and s == 0:
		sol.append(x)
print(' '.join((str(x) for x in sol)))


import itertools, sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = sum(A)
X = set(itertools.accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


def isOK(a, lis):
	temp = 0
	for x in lis:
		temp += x
		if temp == a:
			temp = 0
		elif temp > a:
			return False
	return temp == 0

def getDivisors(n):
	i = 1
	res1 = []
	while i * i <= n:
		if n % i == 0:
			res1.append(i)
		i += 1
	res2 = []
	for x in res1:
		res2.append(n // x)
	if res2[-1] * res2[-1] == n:
		res2.pop()
	return res1 + list(reversed(res2))
n = int(input())
lis = list(map(int, input().split()))
a = 0
b = sum(lis)
res = []
divs = getDivisors(b)
for x in divs:
	if isOK(x, lis):
		res.append(x)
print(' '.join(map(str, res)))


def check_size(l, i):
	s = 0
	j = 0
	n = len(l) - i + 1
	while j < len(l):
		while j < len(l) and s < i:
			s += l[j]
			j += 1
		if s > i:
			return False
		else:
			s = 0
	return True

def div(l):
	i = 1
	s = sum(l)
	p = ''
	ans = []
	while i * i <= s:
		if s % i == 0:
			if check_size(l, i):
				ans.append(int(i))
			x = s / i
			if i != x and check_size(l, x):
				ans.append(int(x))
		i += 1
	ans = sorted(ans)
	for i in ans:
		p += str(i) + ' '
	print(p)

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


from math import sqrt
t = input()
B = [int(x) for x in input().split()]
cum = {}
s = 0
for x in B:
	s = s + x
	cum[s] = 1
res = []

def onboard(s, i, cum, res):
	if s % i == 0:
		found = True
		for j in range(i, s, i):
			if j not in cum:
				found = False
				break
		if found:
			res.append(i)
for i in range(1, int(sqrt(s)) + 1):
	onboard(s, i, cum, res)
	if i != s // i:
		onboard(s, s // i, cum, res)
print(' '.join(map(str, sorted(res))))


N = int(input())
G = []
S = [0]
for s in input().split():
	g = int(s)
	G.append(g)
	S.append(S[-1] + g)
S = S[1:]
import bisect, math
M = S[-1]
L = len(S)
V = set()
V.add(M)
for x in range(1, int(math.sqrt(M)) + 2):
	if M % x != 0:
		continue
	d = M // x
	v = True
	for i in range(1, x):
		ac = i * d
		ind = bisect.bisect_left(S, ac)
		if ind == L or S[ind] != ac:
			v = False
			break
	if v:
		V.add(d)
	v = True
	for i in range(1, d):
		ac = i * x
		ind = bisect.bisect_left(S, ac)
		if ind == L or S[ind] != ac:
			v = False
			break
	if v:
		V.add(x)
print(' '.join(list(map(lambda x: str(x), sorted(list(V))))))


import itertools, sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = sum(A)
X = set(itertools.accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


from functools import reduce
n = int(input())
a = tuple(map(int, input().split()))

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

def is_valid(f):
	count = 0
	for num in a:
		count += num
		if count > f:
			return False
		if count == f:
			count = 0
	return True
amax = max(a)
asum = sum(a)
factors_set = {n for n in factors(asum) if n >= amax and is_valid(n)}
print(' '.join(list(map(str, sorted(factors_set)))))


from math import sqrt, ceil

def can_partition(array, factor):
	curr_total = 0
	for num in array:
		curr_total += num
		if curr_total == factor:
			curr_total = 0
		elif curr_total > factor:
			return False
	return True

def factors(num):
	small = []
	big = []
	for factor in range(1, ceil(sqrt(num))):
		if num % factor == 0:
			small.append(factor)
			big.append(num // factor)
	if sqrt(num) == int(sqrt(num)):
		small.append(int(sqrt(num)))
	return small + big[::-1]
num_groups = int(input())
array = list(map(int, input().split()))
bus_sizes = []
for factor in factors(sum(array)):
	if can_partition(array, factor):
		bus_sizes.append(factor)
print(' '.join((str(bs) for bs in bus_sizes)))


import itertools, sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = sum(A)
X = set(itertools.accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


from math import sqrt

def factorize(n):
	if n < -1:
		return [(-1, 1)] + factorize(-n)
	elif n == -1:
		return [(-1, 1)]
	elif n == 0:
		return [(0, 1)]
	elif n == 1:
		return [(1, 1)]
	else:

		def potential_primes():
			base_primes = (2, 3, 5)
			for base_prime in base_primes:
				yield base_prime
			base_primes = (7, 11, 13, 17, 19, 23, 29, 31)
			prime_group = 0
			while True:
				for base_prime in base_primes:
					yield (prime_group + base_prime)
				prime_group += 30
		factors = []
		sqrtn = sqrt(n)
		for divisor in potential_primes():
			if divisor > sqrtn:
				break
			power = 0
			while n % divisor == 0:
				n //= divisor
				power += 1
			if power > 0:
				factors.append((divisor, power))
				sqrtn = sqrt(n)
		if n > 1:
			factors.append((n, 1))
		return factors

def divisors_from_factors(factors):

	def unsorted_divisors_from_factors(factors):
		if not factors:
			return [1]
		else:
			(base, max_power) = factors[0]
			if base == -1:
				return unsorted_divisors_from_factors(factors[1:])
			elif base == 0:
				return []
			elif base == 1:
				return unsorted_divisors_from_factors(factors[1:])
			else:
				divisors = unsorted_divisors_from_factors(factors[1:])
				all_divisors = []
				for power in range(0, max_power + 1):
					all_divisors += map(lambda x: x * base ** power, divisors)
				return all_divisors
	all_divisors = unsorted_divisors_from_factors(factors)
	all_divisors.sort()
	return all_divisors
N = int(input())
A = [int(ns) for ns in str(input()).split()]
m = max(A)
s = sum(A)
S = divisors_from_factors(factorize(s))
ans = []
for i in S:
	if i < m:
		continue
	g = True
	cs = 0
	for a in A:
		cs += a
		if cs > i:
			g = False
			break
		elif cs == i:
			cs = 0
	if g and cs == 0:
		ans.append(i)
print(' '.join((str(x) for x in ans)))


from itertools import accumulate

def divisors(x):
	assert x > 0
	if x == 1:
		return [1]
	if x <= 3:
		return [1, x]
	res = [1, x]
	i = 2
	while i * i < x:
		if not x % i:
			res.extend([i, x // i])
		i += 1
	if i * i == x:
		res.append(i)
	res.sort()
	return res

def valid_size(data, d):
	j = 0
	for i in range(d, data[-1], d):
		while data[j] < i:
			j += 1
		if data[j] > i:
			return False
	return True
n_groups = int(input())
data = list(accumulate(map(int, input().split())))
bus_size = []
for d in divisors(data[-1]):
	if valid_size(data, d):
		bus_size.append(d)
print(*bus_size)


def get_partial_sums(iterable):
	i = 0
	for n in iterable:
		i += n
		yield i

def get_divisors(n):
	divisors = []
	i = 1
	while i * i <= n:
		if n % i == 0:
			yield i
			divisors.append(i)
		i += 1
	for d in reversed(divisors):
		if d * d == n:
			continue
		yield (n // d)

def get_busses(n, arr):
	total = sum(arr)
	partial_sums = set(get_partial_sums(arr))
	divisors = get_divisors(total)
	for d in divisors:
		for m in range(d, total, d):
			if m not in partial_sums:
				break
		else:
			yield d
n = int(input())
arr = tuple((int(a) for a in input().strip().split()))
print(' '.join((str(x) for x in get_busses(n, arr))))


def getparti(x):
	temps = 0
	for i in range(0, n):
		temps = temps + a[i]
		if temps == x:
			temps = 0
		if temps > x:
			return False
	return True
n = int(input())
a = [int(elem) for elem in input().split()]
accums = set()
s = 0
maxa = a[0]
for i in range(0, n):
	s = s + a[i]
	accums.add(s)
	if maxa < a[i]:
		maxa = a[i]
partilist = set()
maxd = int(s ** 0.5)
for d in range(1, maxd + 1):
	if s % d == 0:
		if d >= maxa and getparti(d) == True:
			partilist.add(d)
		if getparti(s // d) == True:
			partilist.add(s // d)
partilist2 = list(partilist)
partilist2.sort()
print(*partilist2)


import itertools
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
X = set(itertools.accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


from math import sqrt, ceil

def divisors(n):
	divs = []
	sq = ceil(sqrt(n))
	for i in range(1, sq):
		if n % i == 0:
			divs.append(i)
			divs.append(n // i)
	if sq * sq == n:
		divs.append(sq)
	return sorted(divs)

def suitable(x):
	multiple = x
	while multiple < s:
		if multiple not in csums:
			return False
		multiple += x
	return True
n = int(input())
csums = set()
s = 0
for a in map(int, input().split()):
	s += a
	csums.add(s)
sizes = []
for x in divisors(s):
	if suitable(x):
		sizes.append(x)
print(*sizes)


input()
people = input().split()
people = [int(x) for x in people]
total = 0
ls = []
for x in people:
	total += x
for x in range(1, 1 + len(people)):
	if total % x == 0:
		hopeful = total / x
		temporary = 0
		for y in people:
			temporary += y
			if temporary == hopeful:
				temporary = 0
		if temporary == 0:
			ls.append(hopeful)
	else:
		pass
ls.sort()
ls = [int(x) for x in ls]
for x in ls:
	print(x, end=' ')


from itertools import combinations

def prime_factorization(n):
	d = 2
	factors = []
	while n > 1:
		while n % d == 0:
			factors.append(d)
			n //= d
		d += 1
		if d ** 2 > n:
			if n != 1:
				factors.append(n)
			break
	return factors

def check(n, answers):
	if n not in answers:
		i = n
		while i != max_val and i in vals:
			i += n
		if i == max_val:
			answers.add(n)
			return True
	return False
n = int(input())
arr = [int(x) for x in input().split()]
sums = [arr[0]]
for val in arr[1:]:
	sums.append(sums[-1] + val)
max_val = sums[-1]
vals = set(sums)
factors = prime_factorization(max_val)
answers = set([max_val])
if max_val == n:
	answers.add(1)
for reps in range(1, len(factors) + 1):
	for x in combinations(factors, reps):
		f = 1
		for y in x:
			f *= y
		check(f, answers)
print(*sorted(answers))


import math
from collections import deque

def _find_factors(n):
	factors = set((1, n))
	for c in range(2, int(math.sqrt(n)) + 1):
		d = n / c
		if d.is_integer():
			factors.add(int(d))
			factors.add(c)
	return factors

def get_bus_sizes(a):
	(smin, smax) = (max(a), sum(a))
	cumulative_sum = [0 for _ in a]
	cumulative_sum[0] = a[0]
	for i in range(1, len(a)):
		cumulative_sum[i] = cumulative_sum[i - 1] + a[i]
	cumulative_sum = set(cumulative_sum)
	factors = _find_factors(smax)
	sizes = deque()
	for factor in factors:
		n = smax // factor
		for i in range(1, n + 1):
			if i * factor not in cumulative_sum:
				break
		else:
			sizes.append(factor)
	return sorted(sizes)
_ = int(input())
a = [int(n) for n in input().split()]
print(' '.join(map(str, get_bus_sizes(a))))


import sys
import math

def divisors(s, m):
	l = []
	for i in range(1, int(math.sqrt(s)) + 1):
		if s % i == 0:
			d1 = i
			d2 = int(s / i)
			if d1 >= m:
				l.append(d1)
			if d2 >= m and d1 != d2:
				l.append(d2)
	l = sorted(l)
	return l

def subset(a, group_size):
	r = 0
	total = 0
	for i in range(0, len(a)):
		total += a[i]
		if total == group_size:
			if i == len(a) - 1:
				return 1
			else:
				total = 0
		elif total > group_size:
			return 0
line = 0
for text in sys.stdin:
	if line > 0:
		a = text.split()
		for i in range(0, len(a)):
			a[i] = int(a[i])
		s = sum(a)
		m = max(a)
		divisor_list = divisors(s, m)
		result = ''
		for d in divisor_list:
			if subset(a, d):
				result += str(d) + ' '
		result = result[0:len(result) - 1]
		print(result)
	line += 1


from math import sqrt

def factors(n):
	r = []
	for x in range(2, int(sqrt(n)) + 1):
		if n % x == 0:
			r.append(x)
			if x * x != n:
				r.append(n // x)
	return r

def inset(s, sm, val):
	v = val
	while val <= sm:
		if not val in s:
			return False
		val += v
	return True
N = int(input())
nums = [int(x) for x in input().split(' ')]
st = set()
s = 0
for num in nums:
	s += num
	st.add(s)
fact = factors(s)
fact.append(1)
r = set()
for v in fact:
	if inset(st, s, v):
		r.add(v)
r.add(s)
rs = sorted(r)
for item in rs:
	print(item, end=' ')


def factors(n):
	factorList = []
	for d in range(1, int((n - 1 / 2) ** (1 / 2)) + 1):
		if n % d == 0:
			factorList += [d, n // d]
	if int(n ** (1 / 2)) ** 2 == n:
		factorList += [int(n ** (1 / 2))]
	factorList.sort()
	return factorList
n = int(input())
groups = [int(x) for x in input().split()]
partialSums = n * [groups[0]]
for i in range(1, n):
	partialSums[i] = partialSums[i - 1] + groups[i]
total = partialSums[-1]
factorList = factors(total)
for d in factorList:
	modSums = [x % d for x in partialSums]
	if modSums.count(0) == total // d:
		print(d, end=' ')


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

def divs(n):
	res = [1]
	i = 2
	while i * i <= n:
		ac = 0
		while n % i == 0:
			ac += 1
			n //= i
		for x in range(len(res) * ac):
			res.append(res[x] * i)
		i += 1
	if n > 1:
		for x in range(len(res)):
			res.append(res[x] * n)
	return res

def k(n):
	ac = n
	for x in a:
		ac -= x
		if ac < 0:
			return False
		if ac == 0:
			ac = n
	return True
for x in sorted(divs(sum(a))):
	if k(x):
		print(x, end=' ')


from math import sqrt

def factors(n):
	factorsList = []
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			factorsList.append(i)
			if i != n // i:
				factorsList.append(n // i)
	factorsList.sort()
	return factorsList
n = int(input())
l = tuple(map(int, input().split(' ')))
cumulativeArray = set()
answer = []
summation = 0
for i in l:
	summation += i
	cumulativeArray.add(summation)
l = factors(summation)
for i in l:
	if all((j in cumulativeArray for j in range(i, l[len(l) - 1], i))):
		answer.append(i)
for i in answer:
	print(i, end=' ')


import itertools, sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = sum(A)
X = set(itertools.accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


size = int(input())
l = list(map(int, input().split(' ')))
m = max(l)
s = sum(l)
res = [s]
tested = 2
x = s // tested
while x >= m:
	if s % x == 0:
		fill = 0
		j = 0
		go_on = True
		while fill < x and go_on and (j < size):
			fill = fill + l[j]
			j = j + 1
			if fill == x:
				fill = 0
			elif fill > x:
				go_on = False
		if j == size and fill == 0:
			res = [x] + res
	old_x = x
	while old_x == x:
		tested = tested + 1
		x = s // tested
print(*res)


from math import sqrt, ceil

def check(a, block):
	cur = 0
	for i in range(len(a)):
		if cur + a[i] > block:
			return False
		cur += a[i]
		if cur == block:
			cur = 0
	return cur == 0
n = int(input())
a = tuple(map(int, input().split()))
suma = sum(a)
result = set()
for d in range(1, ceil(sqrt(suma)) + 1):
	if suma % d == 0:
		if check(a, d):
			result.add(d)
		if suma // d != d and check(a, suma // d):
			result.add(suma // d)
print(*list(sorted(result)), sep=' ')


def factors(n):
	facs = set()
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			facs.add(i)
			facs.add(n // i)
	return facs

def is_valid(groups, bus_size):
	current_bus = 0
	for group in groups:
		current_bus += group
		if current_bus > bus_size:
			return False
		if current_bus == bus_size:
			current_bus = 0
	return current_bus == 0
input()
a = [int(x) for x in input().strip().split()]
max_bus_size = sum(a)
bus_sizes = sorted([f for f in factors(max_bus_size) if is_valid(a, f)])
print(' '.join([str(x) for x in bus_sizes]))


n = int(input())
a = [int(x) for x in input().split()]
(f, ans) = ([a[0]], [])
largest = a[0]
for i in range(1, len(a)):
	f.append(a[i] + f[i - 1])
	largest = max(largest, a[i])
for i in f:
	if f[-1] % i == 0 and i >= largest:
		count = 0
		for x in a:
			count = count + x
			if count == i:
				count = 0
			elif count > i:
				break
		if count == 0:
			ans.append(i)
print(*ans)


import math
n = int(input())
arr = map(int, input().strip().split(' '))
arr = list(arr)
s = sum(arr)
mx = max(arr)
x = []
for i in range(1, int(math.sqrt(s)) + 1):
	if s % i == 0:
		if i >= mx:
			x.append(i)
		if s / i >= mx and i != 1:
			x.append(int(s / i))
x.append(s)
d1 = set(x)
for i in sorted(d1):
	f = 0
	flag = False
	for j in arr:
		f += j
		if f == i:
			f = 0
			flag = True
		if f > i:
			flag = False
			break
	if flag == True:
		print(i, end=' ')


import sys

def isOK(m, a, n):
	t = 0
	for i in range(n):
		if t == 0:
			t = m
		t -= a[i]
		if t < 0:
			break
	if i == n - 1 and t == 0:
		return True
	return False
n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
s = sum(a)
ans = []
for p in range(1, int(pow(s, 0.5)) + 1):
	if s % p == 0:
		q = s / p
		if isOK(p, a, n):
			ans.append(p)
		if q != p and isOK(q, a, n):
			ans.append(q)
ans.sort()
for i in range(len(ans)):
	print(int(ans[i]), end=' ')


n = int(input())
a = list(map(int, input().split()))
s = a[:]
for i in range(1, n):
	s[i] += s[i - 1]
myset = set()
for i in range(n):
	myset.add(s[i])
for i in range(n):
	if s[-1] % s[i] != 0:
		continue
	can = True
	for j in range(2, s[-1] // s[i]):
		can = s[i] * j in myset
		if can == False:
			break
	if can:
		print(s[i], end=' ')


def binSearch(v, s, e):
	m = s + (e - s + 1) // 2
	while s <= e and B[m] != v:
		if B[m] > v:
			e = m - 1
		else:
			s = m + 1
		m = s + (e - s + 1) // 2
	return m if s <= e else -1

def possible(l, x):
	while l < n - 1:
		l = binSearch(B[l] + x, l + 1, n - 1)
		if l == -1 or (C[l] - A[l]) % x > 0:
			return False
	return True
n = int(input())
A = [int(x) for x in input().split()]
B = [0] * n
C = [0] * n
B[0] = A[0]
C[n - 1] = A[n - 1]
m = max(A)
for i in range(1, n):
	B[i] = B[i - 1] + A[i]
	C[n - i - 1] = C[n - i] + A[n - i - 1]
for i in range(n):
	if B[i] >= m and (C[i] - A[i]) % B[i] == 0 and possible(i, B[i]):
		print(B[i], end=' ')


from itertools import accumulate
(_, cumsum) = (input(), set(accumulate(map(int, input().split()))))
total = max(cumsum)
print(' '.join(map(str, sorted(filter(lambda i: total % i == 0 and all((j in cumsum for j in range(i, total, i))), cumsum)))))


from math import ceil, sqrt
n = int(input())
arr = [int(x) for x in input().split(' ')]

def test(s):
	ts = 0
	for i in arr:
		ts += i
		if ts == s:
			ts = 0
		elif ts > s:
			return False
	if ts < s and ts != 0:
		return False
	return True
sol = []
s = sum(arr)
for i in range(1, ceil(sqrt(s)) + 1):
	if i not in sol and test(i):
		sol.append(i)
	if s // i not in sol and test(s // i):
		sol.append(s // i)
sol.sort()
print(' '.join(map(str, sol)))


from math import sqrt
n = int(input())
arr = [int(x) for x in input().split(' ')]
lookup = {}
total = arr[0]
lookup[total] = 1
for i in range(1, n):
	total += arr[i]
	lookup[total] = 1
factors = []
factorfinal = []
for j in range(1, int(sqrt(total)) + 1):
	if total % j == 0:
		factors.append(j)
		v = int(total / j)
		if v != j:
			factorfinal.append(v)
factors.extend(factorfinal[::-1])
final = []
d = []
for k in factors:
	flag = True
	for y in range(k, total + 1, k):
		if lookup.get(y) == None:
			flag = False
			break
	if flag == True:
		d.append(k)
c = ' '.join((str(x) for x in d))
print(c)


n = int(input())
(l, cum) = ([], [0] * n)
l = list(map(int, input().split()))
x = 0
if l[0] == 1:
	x = 1
flag = 0
for i in l:
	if i != 1:
		flag = 1
		break
cum[0] = l[0]
for i in range(1, n):
	cum[i] = cum[i - 1] + l[i]
ans = []
for i in cum:
	if cum[len(cum) - 1] % i == 0:
		ans.append(i)
if flag == 0:
	x = 0
final = []
for i in ans:
	(c, f) = (1, 0)
	for j in cum:
		if j == i * c:
			c = c + 1
		elif j > i * c:
			f = 1
			break
	if f == 0:
		final.append(str(i))
print(' '.join(final))


def check(sum_set, mx):
	res = []
	for i in sum_set:
		a = True
		if mx % i != 0:
			continue
		for j in range(1, mx // i):
			if j * i not in sum_set:
				a = False
				break
		if a:
			res.append(i)
	return sorted(res)
N = int(input())
s = 0
t = set()
for i in input().split():
	s += int(i)
	t.add(s)
rs = check(t, s)
print(' '.join([str(i) for i in rs]))


n = int(input())
a = [int(x) for x in input().split()]
suma = sum(a)

def valid(mida, ini):
	while ini < len(a):
		(s, i) = (0, ini)
		while s != mida and i < len(a):
			s += a[i]
			i += 1
		if s != mida:
			return False
		ini = i
	return True
bons = []
(esq, drt) = (0, suma)
for i in range(len(a)):
	x = a[i]
	esq += x
	drt -= x
	if drt % esq == 0 and valid(esq, i + 1):
		bons.append(esq)
print(' '.join([str(x) for x in bons]))


import sys

def bus_gen(total):
	r = int(pow(total, 0.5))
	for u in range(1, r + 1):
		yield u
		v = total // u
		if v != u:
			yield v

def match(bus, gg):
	sm = 0
	for g in gg:
		sm += g
		if sm > bus:
			return False
		if sm == bus:
			sm = 0
	return sm == 0

def solve(gg):
	cache = set()
	total = sum(gg)
	for bus in bus_gen(total):
		if match(bus, gg):
			cache.add(bus)
	for bus in sorted(cache):
		print(bus, end=' ')
	print()
_ = int(input())
gg = list(map(int, input().split()))
solve(gg)


N = int(input())
A = [int(s) for s in input().split()]
S = sum(A)
res = []
x = 0
for a in A:
	x += a
	if S % x:
		continue
	k = 0
	for b in A:
		k += b
		if k > x:
			break
		elif k == x:
			k = 0
	if k == 0:
		res.append(x)
print(*res)


N = int(input())
ar = list(map(int, input().split()))
sm = 0
S = sum(ar)

def check(s):
	i = 0
	sm = 0
	while i < N:
		sm += ar[i]
		if sm == s:
			sm = 0
		elif sm > s:
			return False
		i += 1
	if sm == 0:
		return True
	return False
for item in ar:
	sm += item
	if S % sm == 0 and check(sm):
		print(sm, end=' ')


N = int(input().strip())
A = list(map(int, input().strip().split()))
for i in range(1, N):
	A[i] += A[i - 1]
S = A[-1]
A = set(A)
ans = []
divisors = []
for i in range(1, S + 1):
	if i * i > S:
		break
	if S % i == 0:
		if i * i != S:
			divisors.append(S // i)
		success = True
		for j in range(i, S, i):
			if j not in A:
				success = False
				break
		if success:
			ans.append(i)
for i in reversed(divisors):
	success = True
	for j in range(i, S, i):
		if j not in A:
			success = False
			break
	if success:
		ans.append(i)
print(*ans)


import math
from itertools import accumulate

def divisors(N):
	divs = set()
	for i in range(1, int(math.sqrt(N) + 1)):
		if N % i == 0:
			divs.add(i)
			divs.add(N // i)
	return sorted(list(divs))
N = int(input())
A = [int(a) for a in input().split()]
S = sum(A)
csum = set(accumulate(A))
divs = divisors(S)
for div in divs:
	flag = True
	for i in range(div, S + 1, div):
		if i not in csum:
			flag = False
			break
	if flag:
		print(div, end=' ')


import math

def divisors(n):
	divisors = {1, n}
	for i in range(2, math.floor(math.sqrt(n)) + 1):
		if n % i == 0:
			divisors.add(i)
			divisors.add(n // i)
	return divisors
n = int(input())
l = [int(i) for i in input().split()]
partial_sums = [l[0]]
for i in range(1, n):
	partial_sums.append(partial_sums[-1] + l[i])
s = partial_sums[-1]
partial_sums = set(partial_sums)
div = divisors(s)
ans = set()
for d in div:
	if d in ans:
		continue
	flag = True
	for i in range(1, s // d + 1):
		if d * i not in partial_sums:
			flag = False
			break
	if flag:
		for i in range(1, s // d + 1):
			if d * i in div:
				ans.add(d * i)
ans = sorted(list(ans))
print(*ans)


arr_len = int(input())
arr = [int(i) for i in input().split()]
arr_sum = sum(arr)
sizes = []
test_size = 0
for i in range(arr_len):
	test_size += arr[i]
	if arr_sum % test_size != 0:
		continue
	sum_ppl = 0
	for j in range(i + 1, arr_len):
		sum_ppl += arr[j]
		if sum_ppl > test_size:
			break
		elif sum_ppl == test_size:
			sum_ppl = 0
	if sum_ppl == 0:
		sizes.append(test_size)
print(' '.join(map(str, sizes)))


n = int(input())
a = tuple(map(int, input().split()))
sizes = []
sum = 0
for group in a:
	sum += group
	sizes.append(sum)
for x in sizes:
	if sum % x == 0:
		busleft = 0
		for group in a:
			if busleft == 0:
				busleft = x
			if group > busleft:
				break
			busleft -= group
		else:
			if busleft == 0:
				print(x, end=' ')


def factors(x):
	yield 1
	if x <= 3:
		return
	root = int(pow(x, 0.5))
	for i in range(2, root):
		if not x % i:
			yield i
			new = x // i
			yield new
	if not x % root:
		yield root
		new = x // root
		if new != root:
			yield new

def x(a):
	s = sum(a)
	yield s
	f = set(factors(s))
	d = {}
	partial = 0
	for i in range(len(a) - 1):
		partial += a[i]
		if partial in f:
			if 2 * partial == s:
				yield partial
			else:
				d[2 * partial] = [partial]
		if partial in d:
			fs = d.pop(partial)
			for factor in fs:
				new_sum = factor + partial
				if new_sum == s:
					yield factor
				elif new_sum in d:
					d[new_sum].append(factor)
				else:
					d[new_sum] = [factor]
n = int(input())
a = list(map(int, input().split()))
print(' '.join(map(str, reversed(list(x(a))))))


from itertools import accumulate
from math import sqrt

def find_divisors(n):
	yield 1
	if n == 1:
		return
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			yield i
			if i != n // i:
				yield (n // i)
	yield n

def find_buscap(cset):
	cmax = max(cset)
	for d in find_divisors(cmax):
		if all((i in cset for i in range(d, cmax + 1, d))):
			yield d
n = int(input().strip())
alist = [int(c) for c in input().strip().split(' ')]
cset = set(accumulate(alist))
print(' '.join((str(i) for i in sorted(find_buscap(cset)))))


from math import sqrt, ceil, floor

def sieve(N):
	b = [True] * (N + 1)
	b[0] = False
	b[1] = False
	i = 2
	while i <= N // 2:
		if b[i]:
			for n in range(i ** 2, N + 1, i):
				b[n] = False
		i += 1
	return {i for (i, b) in enumerate(b) if b}

def divisors(F):
	D = {1}
	for f in F:
		D |= {f * d for d in D}
	return D

def factor(n, P):
	if n in P:
		return [n]
	f = []
	for p in P:
		while n % p == 0:
			n //= p
			f.append(p)
		if n in P:
			f.append(n)
			return f
	if n != 1:
		f.append(n)
	return f
n = int(input())
A = [int(x) for x in input().split()]
asum = sum(A)
P = sieve(ceil(sqrt(asum)))
F = factor(asum, P)
D = sorted(divisors(F))

def doable(n):
	s = 0
	for a in A:
		s += a
		if s > n:
			return False
		if s == n:
			s = 0
	return True
res = [d for d in D if doable(d)]
print(*res)


import math
q = int(input())
data = [int(x) for x in input().split()]
a = max(data)
b = sum(data)
div = []
i = 1
while i * 25 < b:
	if b % i == 0:
		div.append(i)
	i += 1
if b % 25 == 0:
	div.append(b // 25)
if b % 24 == 0:
	div.append(b // 24)
if b % 23 == 0:
	div.append(b // 23)
if b % 22 == 0:
	div.append(b // 22)
if b % 21 == 0:
	div.append(b // 21)
if b % 20 == 0:
	div.append(b // 20)
if b % 19 == 0:
	div.append(b // 19)
if b % 18 == 0:
	div.append(b // 18)
if b % 17 == 0:
	div.append(b // 17)
if b % 16 == 0:
	div.append(b // 16)
if b % 15 == 0:
	div.append(b // 15)
if b % 14 == 0:
	div.append(b // 14)
if b % 13 == 0:
	div.append(b // 13)
if b % 12 == 0:
	div.append(b // 12)
if b % 11 == 0:
	div.append(b // 11)
if b % 10 == 0:
	div.append(b // 10)
if b % 9 == 0:
	div.append(b // 9)
if b % 8 == 0:
	div.append(b // 8)
if b % 7 == 0:
	div.append(b // 7)
if b % 6 == 0:
	div.append(b // 6)
if b % 4 == 0:
	div.append(b // 4)
if b % 5 == 0:
	div.append(b // 5)
if b % 3 == 0:
	div.append(b // 3)
if b % 2 == 0:
	div.append(b // 2)
div.append(b)
aind = 0
ind = 0
pos = []
while aind < len(div):
	busslats = 0
	a = div[aind]
	if a == 0:
		aind += 1
		continue
	while busslats < a and ind < q:
		busslats += data[ind]
		ind += 1
	if busslats < a:
		aind += 1
		ind = 0
		continue
	if busslats > a:
		aind += 1
		ind = 0
		continue
	if ind == q:
		pos.append(a)
		aind += 1
		ind = 0
		continue
print(*sorted(set(pos)))


n = int(input())
l = [int(x) for x in input().split()]
r = []
_max = int(sum(l))
_min = int(max(l))
R = int(0)
L = int(_max)
for i in l[::-1]:
	if L == 0:
		break
	elif R % L == 0:
		b = int(0)
		for j in l:
			b = b + j
			if b == L:
				b = 0
			elif b > L:
				break
		if b == 0:
			r.append(L)
	L -= i
	R += i
for i in r[::-1]:
	print(i, end=' ')


from bisect import bisect_left
from math import sqrt

def f(trips, S, bus_size, x):
	for t in range(1, trips):
		if S[bisect_left(S, t * bus_size)] != t * bus_size:
			break
	else:
		x.append(bus_size)
total = 0
S = []
n = int(input())
an = [int(x) for x in input().strip().split()]
for a in an:
	total += a
	S.append(total)
x = []
for trips in range(1, int(sqrt(total)) + 1):
	if total % trips == 0:
		bus_size = total // trips
		f(trips, S, bus_size, x)
		if bus_size * bus_size != total:
			f(bus_size, S, trips, x)
x.sort()
for xn in x:
	print(xn, end=' ')


import math
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
sum_a = sum(a)
x_lst = set()
for i in range(1, int(math.sqrt(sum_a) + 1)):
	(d, m) = divmod(sum_a, i)
	if m == 0:
		x_lst.add(i)
		x_lst.add(d)
max_a = max(a)
result = []
for x in sorted(x_lst):
	if x < max_a:
		continue
	bus_x = 0
	for v in a:
		bus_x += v
		if bus_x == x:
			bus_x = 0
		elif bus_x > x:
			break
	if bus_x == 0:
		result.append(str(x))
print(' '.join(result))


n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
massimo = sum(a)
rimanente = massimo
fine = int(massimo ** 0.5 + 1)
fattori = []
i = 2
while rimanente != 1:
	while rimanente % i == 0:
		fattori.append(i)
		rimanente //= i
	if i > massimo:
		fattori.append(rimanente)
		break
	i += 1

def scorri(inizio, precedenti):
	divisori.append(precedenti * fattori[inizio])
	for i in range(inizio + 1, len(fattori)):
		if i == inizio + 1 or fattori[i] != fattori[i - 1]:
			scorri(i, precedenti * fattori[inizio])
divisori = []
for i in range(len(fattori)):
	if i == 0 or fattori[i] != fattori[i - 1]:
		scorri(i, 1)
divisori.append(1)
divisori.sort()
risultati = []
a_max = max(a)
for dimensione in divisori:
	if dimensione < a_max:
		continue
	viaggio = 0
	trovato = True
	for x in a:
		if viaggio + x < dimensione:
			viaggio += x
		elif viaggio + x == dimensione:
			viaggio = 0
		else:
			trovato = False
			break
	if viaggio == 0 and trovato:
		risultati.append(dimensione)
print(' '.join([str(x) for x in risultati]))


N = int(input())
A = [int(x) for x in input().split()]
amax = 0
mysum = sum(A)
progsums = []
psum = 0
for a in A:
	psum += a
	progsums += [psum]
	if a > amax:
		amax = a
plen = len(progsums)
if plen % 2 == 0:
	max_div = mysum // 2
else:
	max_div = mysum // 3 + 1
for j in range(plen):
	i = progsums[j]
	if i < amax:
		continue
	if mysum % i != 0:
		continue
	if i > mysum // 2 + 1:
		break
	mult = i + i
	for k in range(j + 1, plen):
		thissum = progsums[k]
		if thissum > mult:
			break
		if thissum == mult:
			if thissum == mysum:
				print(i, end=' ')
			mult += i
print(mysum)


import math

def get_factors(n):
	factors = []
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			factors.append(i)
			factors.append(n // i)
	factors = list(set(factors))
	factors.sort()
	return factors

def is_goodx(group, x, max_a):
	if x < max_a:
		return False
	start_with = 0
	x_copy = x
	while True:
		while x_copy > 0:
			x_copy -= group[start_with]
			start_with += 1
		if x_copy < 0:
			return False
		if start_with == len(group):
			return True
		x_copy = x
n = int(input())
group = [int(a) for a in input().split()]
max_a = max(group)
sum_a = sum(group)
factors = get_factors(sum_a)
ans = []
for factor in factors:
	if is_goodx(group, factor, max_a) == True:
		ans.append(factor)
		print(factor, end=' ')


n = int(input())
gr = list(map(int, input().split()))
totalSum = sum(gr)
capacity = 0
for i in range(0, n):
	capacity = capacity + gr[i]
	if totalSum % capacity != 0:
		continue
	else:
		Sum = 0
		for j in range(i + 1, n):
			if gr[i] > capacity:
				Sum = None
				break
			if Sum == capacity:
				Sum = 0
			Sum = Sum + gr[j]
		if Sum == capacity or Sum == 0:
			print(capacity, end=' ')


import math

def divisorGenerator(n):
	large_divisors = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				large_divisors.append(n / i)
	for divisor in reversed(large_divisors):
		yield divisor
q = int(input())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
x = 0
wynik = []
wynikr = []
for i in range(q):
	x = x + a[i]
wynik = list(map(int, divisorGenerator(x)))
for j in range(len(wynik) - 1):
	b = 0
	for i in range(len(a)):
		b = b + a[i]
		if b > wynik[j]:
			break
		elif b == wynik[j]:
			if i == len(a) - 1:
				wynikr.append(wynik[j])
			else:
				b = 0
wynikr.append(x)
print(*wynikr)


n = int(input())
people = input()
groups = []
groupCount = set()
maxPeopleCount = 0
totalPeopleCount = 0
for count in people.split(' '):
	temp = int(count)
	groups.append(temp)
	totalPeopleCount += temp
	if temp > maxPeopleCount:
		maxPeopleCount = temp
	groupCount.add(totalPeopleCount)
solutions = []
for candidate in groupCount:
	if candidate < maxPeopleCount:
		continue
	if totalPeopleCount % candidate != 0:
		continue
	tripCount = 0
	peopleTravelled = 0
	while tripCount < totalPeopleCount / candidate:
		peopleTravelled += candidate
		if peopleTravelled not in groupCount:
			break
		tripCount += 1
	if peopleTravelled == totalPeopleCount:
		solutions.append(candidate)
solutions.sort()
for sol in solutions:
	print(sol, end=' ')


from itertools import accumulate

def divisors(n):
	i = 1
	divs = set()
	while i <= n / i:
		if n % i == 0:
			divs.add(i)
			divs.add(n // i)
		i += 1
	return divs

def test_div(n, m, acc):
	for i in range(n, m + 1, n):
		if i not in acc:
			return False
	return True
t = input()
groups = map(int, input().split())
acc = set(accumulate(groups))
bus = max(acc)
divs = sorted(list(divisors(bus)))
for d in divs:
	if test_div(d, bus, acc):
		print(d, end=' ')


from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
X = set(accumulate(A))
for x in sorted(X):
	if S % x == 0:
		for i in range(1, S // x + 1):
			if i * x not in X:
				break
		else:
			print(x, end=' ' if x < S else '\n')


n = int(input())
A = [int(x) for x in input().split(' ')]

def bus_station_problem(A, n):
	L = sum(A)
	R = 0
	ret = ''
	for i in A[::-1]:
		if L == 0:
			break
		if R % L == 0:
			b = 0
			for j in A:
				b += j
				if b == L:
					b = 0
				elif b > L:
					break
			if b == 0:
				ret = str(L) + ' ' + ret
		L -= i
		R += i
	return ret
print(bus_station_problem(A, n))


n = int(input().strip())
sizes = [int(a) for a in input().strip().split()]

def cum_sum(a):
	sums = []
	for ai in a:
		previous_sum = sums[-1] if sums else 0
		sums.append(ai + previous_sum)
	return sums
cum_sizes = cum_sum(sizes)
cum_sizes_set = set(cum_sizes)

def is_valid(bus_size):
	(ratio, remainder) = divmod(cum_sizes[-1], bus_size)
	if remainder != 0:
		return False
	for r in range(ratio - 1, 1, -1):
		if r * bus_size not in cum_sizes_set:
			return False
	return True
valid_bus_sizes = []
for candidate_size in cum_sizes:
	if is_valid(candidate_size):
		valid_bus_sizes.append(candidate_size)
print(' '.join(map(str, valid_bus_sizes)))


n = int(input())
A = list(map(int, input().split()))
xs = set()
res = list()
s = 0
for i in range(n):
	s += A[i]
	xs.add(s)
for x in xs:
	if s % x == 0:
		j = 1
		while j < s / x + 1 and j * x in xs:
			j += 1
		if j == s / x + 1:
			res.append(x)
res = sorted(res)
print(' '.join((str(x) for x in res)))


import sys, math
from itertools import accumulate
inputvalues = sys.stdin.readlines(10000000000000)
ng = int(inputvalues[0].replace('\n', ''))
np = list(map(int, inputvalues[1].split()))

def test_number(np_bus, np_group_left):
	test_num = np_bus
	for i in range(len(np_group_left)):
		test_num -= np_group_left[i]
		if test_num == 0 and i != len(np_group_left) - 1:
			test_num = np_bus
			continue
		else:
			if test_num == 0 and i == len(np_group_left) - 1:
				test_out = True
			if test_num < 0:
				test_out = False
	return test_out
x = []
x.append(sum(np))
np_left_arr = list(accumulate(np[::-1]))
test_x = list(accumulate(np))[::-1]
for i in range(ng - 1):
	if np_left_arr[i] % test_x[i + 1] == 0 and test_x[i + 1] >= max(np):
		test_thisx = test_number(test_x[i + 1], np[-(i + 1):])
		if test_thisx:
			x.append(test_x[i + 1])
sol = str.join(' ', map(str, x[::-1]))
print(sol)


def bsp(A, n):
	L = sum(A)
	R = 0
	ret = ''
	for i in A[::-1]:
		if L == 0:
			break
		if R % L == 0:
			b = 0
			for j in A:
				b += j
				if b == L:
					b = 0
				elif b > L:
					break
			if b == 0:
				ret = str(L) + ' ' + ret
		L -= i
		R += i
	return ret
n = int(input())
g = []
for s in input().split():
	g.append(int(s))
print('{0}'.format(bsp(g, n)))


n = int(input().strip())
a = list(map(int, input().strip().split()))
pe = sum(a)
k = 1
o = {pe}
while k * k <= pe:
	if pe % k == 0:
		m = k
		out = True
		j = 0
		while out and j < n:
			m -= a[j]
			if m < 0:
				out = False
			if m == 0:
				m = k
			j += 1
		if out:
			o.add(k)
		m = pe // k
		out = True
		j = 0
		while out and j < n:
			m -= a[j]
			if m < 0:
				out = False
			if m == 0:
				m = pe // k
			j += 1
		if out:
			o.add(pe // k)
	k += 1
o = list(o)
o.sort()
print(' '.join(list(map(str, o))))


def busStation(A, n):
	L = sum(A)
	m = max(A)
	R = 0
	bus = list()
	for i in A[::-1]:
		if L < m:
			break
		if R % L == 0:
			b = 0
			for j in A:
				b += j
				if b == L:
					b = 0
				elif b > L:
					break
				else:
					pass
			if b == 0:
				bus.append(L)
		L -= i
		R += i
	return ' '.join(list(map(str, bus[::-1])))
n = int(input())
a = list(map(int, input().split()))
print(busStation(a, n))


n = int(input())
A = list(map(int, input().strip().split(' ')))
total = A

def find(N):
	T = []
	K = int(N ** 0.5)
	temp1 = []
	temp2 = []
	for i in range(1, K + 1):
		if N % i == 0:
			temp1 += [i]
			temp2 += [N // i]
	check = 0
	if temp1[-1] == temp2[-1]:
		check = 1
	if check == 0:
		temp = temp1 + temp2[::-1]
	else:
		temp = temp1 + temp2[:-1][::-1]
	return temp
div = find(sum(A))
pre = []
temp = 0
for i in range(len(A)):
	temp += A[i]
	pre += [temp]
total = sum(A)
ANS = []
for x in div:
	temp = total // x
	j = 1
	for i in range(len(pre)):
		if pre[i] == j * x:
			j += 1
		elif pre[i] > j * x:
			break
	if j == temp + 1:
		ANS += [x]
print(*ANS)


def func(A, n):
	L = sum(A)
	R = 0
	ret = ''
	for i in A[::-1]:
		if L == 0:
			break
		if R % L == 0:
			b = 0
			for j in A:
				b += j
				if b == L:
					b = 0
				elif b > L:
					break
			if b == 0:
				ret = str(L) + ' ' + ret
		L -= i
		R += i
	return ret
n = int(input())
A = list(map(int, input().split()))
print(func(A, n))


def get_factors(n):
	factors = set()
	for i in range(int(n ** 0.5), 0, -1):
		if n % i == 0:
			factors.add(i)
			factors.add(n // i)
	return factors

def bus_sizes(A, n):
	test_sizes = get_factors(sum(A))
	true_sizes = set(list(test_sizes))
	for size in test_sizes:
		passengers = 0
		for j in range(n):
			passengers += A[j]
			if passengers > size:
				true_sizes.remove(size)
				break
			if passengers == size:
				passengers = 0
	return sorted(list(true_sizes))
n = int(input().strip())
A = list(map(int, input().strip().split()))
print(*bus_sizes(A, n))