Bajtek, known for his unusual gifts, recently got an integer array $x_0, x_1, \ldots, x_{k-1}$.

Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $a$ of length $n + 1$. As a formal description of $a$ says, $a_0 = 0$ and for all other $i$ ($1 \le i \le n$) $a_i = x_{(i-1)\bmod k} + a_{i-1}$, where $p \bmod q$ denotes the remainder of division $p$ by $q$.

For example, if the $x = [1, 2, 3]$ and $n = 5$, then:  $a_0 = 0$,  $a_1 = x_{0\bmod 3}+a_0=x_0+0=1$,  $a_2 = x_{1\bmod 3}+a_1=x_1+1=3$,  $a_3 = x_{2\bmod 3}+a_2=x_2+3=6$,  $a_4 = x_{3\bmod 3}+a_3=x_0+6=7$,  $a_5 = x_{4\bmod 3}+a_4=x_1+7=9$. 

So, if the $x = [1, 2, 3]$ and $n = 5$, then $a = [0, 1, 3, 6, 7, 9]$.

Now the boy hopes that he will be able to restore $x$ from $a$! Knowing that $1 \le k \le n$, help him and find all possible values of $k$ — possible lengths of the lost array.


-----Input-----

The first line contains exactly one integer $n$ ($1 \le n \le 1000$) — the length of the array $a$, excluding the element $a_0$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).

Note that $a_0$ is always $0$ and is not given in the input.


-----Output-----

The first line of the output should contain one integer $l$ denoting the number of correct lengths of the lost array.

The second line of the output should contain $l$ integers — possible lengths of the lost array in increasing order.


-----Examples-----
Input
5
1 2 3 4 5

Output
5
1 2 3 4 5 
Input
5
1 3 5 6 8

Output
2
3 5 
Input
3
1 5 3

Output
1
3 


-----Note-----

In the first example, any $k$ is suitable, since $a$ is an arithmetic progression.

Possible arrays $x$:  $[1]$ $[1, 1]$ $[1, 1, 1]$ $[1, 1, 1, 1]$  $[1, 1, 1, 1, 1]$

In the second example, Bajtek's array can have three or five elements.

Possible arrays $x$:  $[1, 2, 2]$ $[1, 2, 2, 1, 2]$

For example, $k = 4$ is bad, since it leads to $6 + x_0 = 8$ and $0 + x_0 = 1$, which is an obvious contradiction.

In the third example, only $k = n$ is good.

Array $[1, 4, -2]$ satisfies the requirements.

Note that $x_i$ may be negative.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
ans = []

for k in range(1, n + 1):
    x = [0] * k

    x[0] = a[0]
    for i in range(1, k):
        x[i] = a[i] - a[i - 1]

    ok = True
    for i in range(k, n):
        if x[i % k] != a[i] - a[i - 1]:
            ok = False
            break
    if ok:
        ans.append(k)

print(len(ans))
print(*ans)


n = int(input())
a = input().split()
b = [0]*n
b[0] = int(a[0])
for i in range(1,n):
    b[i] = int(a[i])-int(a[i-1])
works = 0
out = ""
for j in range(1,n+1):
    bo = True
    for k in range(n):
        if b[k] != b[k%j]:
            bo = False
            break
    if bo:
        works += 1
        out += str(j) + " "
print(works)
print(out[:-1])


n = int(input())

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

diffs = [a[0]]

for i in range(1,n):
    diffs.append(a[i] - a[i-1])

output = []
for l in range(1,n+1):
    flag = True

    for i in range(l, n):
        if diffs[i] != diffs[i-l]:
            flag = False
            break

    if flag:
        output.append(l)

print(len(output))

for i in output:
    print(i, end=" ")


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n = ii()
a = [0] + li()
d = [a[i] - a[i - 1] for i in range(1, n + 1)]

ans = []
for i in range(1, n + 1):
    ok = all(d[j] == d[j % i] for j in range(n))
    if ok: ans.append(i)
print(len(ans))
print(*ans)


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

arr_k = [xs[0]]

for i in range(1, len(xs)):
	arr_k.append(xs[i] - xs[i - 1])

soln = []
# print(arr_k)
for k in range(1, len(arr_k) + 1):
	mul = len(arr_k) // k + 1
	# print(k,arr_k[:k], mul)
	tmp = (arr_k[:k] * mul)[:len(arr_k)]
	# print(k, tmp)
	if tmp == arr_k:
		soln.append(k)
print(len(soln))
print(" ".join(map(str, soln)))

n = int(input())
a = [int(k) for k in input().split()]
answ = []
for k in range(1, n + 1):
    prev = 0
    arr = [0 for i in range(k)]
    good = True
    for i in range(n):
        if i < k:
            arr[i] = a[i] - prev
        else:
            if arr[i % k] != a[i] - prev:
                good = False
                break
        prev = a[i]
    if good:
        answ.append(k)
print(len(answ))
print(*answ)


n = int(input())
arr = [0] + [int(i) for i in input().split(" ")]
diff = [arr[i] - arr[i-1] for i in range(1, len(arr))]
poss = []
for xlen in range(1, len(diff)+1):
    rep = diff[0:xlen]
    for startpos in range(xlen, len(diff), xlen):
        currarr = diff[startpos:min(startpos+xlen, len(diff))]
        for obj in range(len(currarr)):
            if rep[obj] != currarr[obj]:
                break
        else:
            continue
        break
    else:
        poss.append(xlen)
print(len(poss))
print(' '.join([str(i) for i in poss]))


def main():
    n = int(input())
    a = [0] + list([int(x) for x in input().split(" ")])
    d = [a[i+1] - a[i] for i in range(len(a)-1)]
    ans = 1
    alist = []
    for i in range(1, n):
        flag = True
        for j in range(n):
            if j >= i and d[j] != d[j-i]:
                flag = False
                break
        if flag:
            alist.append(i)
            ans += 1
    alist.append(n)
    print(ans)
    print(" ".join([str(x) for x in alist]))


def __starting_point():
    main()

__starting_point()

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2018/10/20 22:37

"""

"""
# Definition for a Node.
"""



N = int(input())
A = [0] + [int(x) for x in input().split()]

def check(k):
    X = [0] * k
    vis = [False] * k
    for i in range(1, N+1):
        ai = A[i]
        x = ai - A[i-1]

        ix = (i-1) % k
        if not vis[ix]:
            vis[ix] = True
            X[ix] = x
        else:
            if X[ix] != x:
                return False
    return True



ans = []
for i in range(1, N+1):
    if check(i):
        ans.append(i)

print(len(ans))
print(' '.join(map(str, ans)))

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
za = [0,] + getIntList()
zb = []
for i in range(N):
    zb.append(za[i+1] - za[i])

dprint(zb)

res = [N]
for i in range(1,N):
    ok = True
    for j in range(i,N):
        if zb[j] != zb[j%i]:
            ok = False
            break
    if ok:
        res.append(i)

res.sort()
print(len(res))
for x in res:
    print(x,end = ' ')


n = int(input())
a = [0] + [int(i) for i in input().split()]
d = [a[i] - a[i-1] for i in range(1, n+1)]
ans = []
for i in range(1, n+1):
    if (d[:i] * (n//i + 20))[:n] == d:
        ans.append(i)
print(len(ans))
print(' '.join([str(i) for i in ans]))


n=int(input())
arr=list(map(int,input().split()))
arr=[0]+arr
ansarr=[]
for i in range(1,n+1):
    valarr=[]
    for j in range(1,i+1):
        val=arr[j]-arr[j-1]
        valarr.append(val)
        flag=0
    #print(valarr)
    for j in range(i+1,n+1):
        if(arr[j]!=valarr[(j-1)%i]+arr[j-1]):
            flag=1
            break

    if(flag==0):
        ansarr.append(i)
print(len(ansarr))
print(*ansarr)




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

for i in range( n - 1, 0, -1 ):
    a[ i ] -= a[ i - 1 ]

lens = []
for l in range( 1, n + 1 ):
    f = True
    for i in range( n ):
        if a[ i ] != a[ i % l ]:
            f = False
    if f:
        lens.append( l )

print( len( lens ) )
for i in lens:
    print( i, end= " ")


n = int(input())
A = input().split()
A = [0] + [int(ai) for ai in A]

valid_k = []

for k in range(1, n + 1):
    X = []
    isvalid = True
    for i in range(1, n + 1):
        if i <= k:
            X.append(A[i] - A[i - 1])
        else:
            #print(A[i] - A[i - 1])
            #print(X[(i - 1) % k])
            if X[(i - 1) % k] != A[i] - A[i - 1]:
                isvalid = False
                break
    #print(X)
    #print(isvalid)
    if isvalid:
        valid_k.append(k)

print(len(valid_k))
print(" ".join([str(k) for k in valid_k]))


n = int(input())
a = list(map(int, input().split()))
a.insert(0,0)
l = []
for i in range(n):
	l.append(a[i + 1] - a[i])
r = []
for i in range(1,n+1):
	m = l[:i]
	j = 0
	k = i
	f = True
	while k<n:
		if m[j] == l[k]:
			j = (j+1)%i
			k += 1
		else:
			f = False
			break
	if f == True:
		r.append(i)
print(len(r))
print(' '.join(map(str,r)))

import sys
import math

def period(x):
    n = len(x)
    res = []
    for i in range(1, len(x)):
        if all(i==j for i,j in zip(x, x[i:])):
            res.append(i)
    return res + [n]

def main():
    [n] = map(int, next(sys.stdin).split())
    a = list(map(int, next(sys.stdin).split()))
    
    a = [0] + a
    x = [j - i for i,j in zip(a, a[1:])]
    
    periods = period(x)
    
    print(len(periods))
    print(' '.join(map(str,periods)))

def __starting_point():
    main()
__starting_point()


import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:list(map(int,input().split()))

n=int(input())
a=[0]+list(mii())

diff=[a[i+1]-a[i] for i in range(n)]

ans=[]
for i in range(1,n+1):
    good=1
    for j in range(n-i):
        if diff[j]!=diff[j+i]:
            good=0
    if good:
        ans.append(i)

print(len(ans))
print(" ".join(map(str,ans)))




def is_cycle(seq, k):
    ii = 0
    for i in range(len(seq)):
        if ii == k: ii = 0
        if seq[i] != seq[ii]: return False
        ii += 1
    return True


n = int(input())

A = [0] + [int(x) for x in input().split()]

AA = []
for i in range(1, len(A)):
    AA.append(A[i] - A[i-1])

# print("A: ", A)
# print("AA: ", AA)
cyqs = []
for cyq in range(1, len(A)):
    if is_cycle(AA, cyq):
        cyqs.append(cyq)
print(len(cyqs))
print(*cyqs)
    
            
        


gcd = lambda a, b: gcd(b, a % b) if b else a


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    brr = []
    for i in range(len(arr) - 1, 0, -1):
        arr[i] -= arr[i - 1]
    for i in range(1, len(arr) + 1):
        f = 1
        for j in range(0, i):
            for k in range(j + i, len(arr), i):
                if arr[j] != arr[k]:
                    f = 0
                    break
        if f:
            brr.append(i)
    print(len(brr))
    print(*brr)





main()

n = int(input())
a = [0]+[int(i) for i in input().split()]


b = [0] * n 
ans = []

for i in range(1,len(a)):
	b[i-1]=a[i]-a[i-1]


for i in range(1,n):
	if b[:i]==b[-i:]:
		ans.append(n-i)

print(len(ans)+1)
print(*sorted(ans),n)

n=int(input())
a=[0]
a+=list(map(int,input().split()))
x=[]
for i in range(1,n+1):
    x.append(a[i]-a[i-1])
ans=[]
b=a[1:]
for i in range(1,n+1):
    r=n%i
    c=x[:i]
    f=0
    if x[:r]!=x[n-r:]:
        continue
    for j in range(i,n-r,i):
        if x[j:j+i]!=c:
            f=1
    if f==0:
        ans.append(i)
print(len(ans))
print(*ans)


n=int(input())
a=[0]+list(map(int,input().split()))
dist=[]
for i in range(1,n+1):
	dist.append(a[i]-a[i-1])
k_s=[]
for k in range(1,n+1):
	can=True
	for i in range(n):
		if dist[i]==dist[i%k]:
			pass
		else:
			can=False
			break
	if can:
		k_s.append(k)
print(len(k_s))
for t in k_s:
	print(t,end=" ")

def tr(s,k):
    a=0
    s1=[]
    for i in range(1,len(s)):
        s1.append(s[i]-s[i-1])
    t=True
    for j in range(1,len(s)):
        if s[j]!=s[j-1]+s1[(j-1)%k]:
            t=False
            break
    return t
from sys import stdin
n=int(stdin.readline().strip())
#n,m=map(int,stdin.readline().strip().split())
s=[0]+list(map(int,stdin.readline().strip().split()))
ans=[]
for i in range(1,n+1):
    if tr(s,i):
        ans.append(i)
print(len(ans))
print(*ans)


#!/usr/bin/env python3
# encoding: utf-8



#----------
# Constants
#----------



#----------
# Functions
#----------

def check(d, length):
    n = len(d)
    t = d[:length]
    for i, item in enumerate(d):
        if t[i % length] != item:
            return False
    return True

# The function that solves the task
def calc(a):
    k = []
    d = []
    last = 0
    for item in a:
        d.append(item - last)
        last = item
    for i in range(len(a)):
        if check(d, i+1):
            k.append(i+1)

    return k


# Reads a string from stdin, splits it by space chars, converts each
# substring to int, adds it to a list and returns the list as a result.
def get_ints():
    return [ int(n) for n in input().split() ]


# Reads a string from stdin, splits it by space chars, converts each substring
# to floating point number, adds it to a list and returns the list as a result.
def get_floats():
    return [ float(n) for n in input().split() ]


def seq2str(seq):
    return ' '.join(str(item) for item in seq)



#----------
# Execution start point
#----------

def __starting_point():
    a = get_ints()
    assert len(a) == 1
    n = a[0]
    a = get_ints()
    assert len(a) == n

    k = calc(a)
    print(len(k))
    print(seq2str(k))
    

__starting_point()