H. Party

Одной из давних традиций старейшей байтландской страховой компании Llong ещё с XVIII века является торжественный обед для судовладельцев, организуемый каждый год в день основания компании.

Согласно традиции, обед проходит за круглым столом, по краю стола расположены n разнообразных блюд, i-е блюдо стоит ci байтландских талеров. Когда судовладелец садится за стол, ему достаются какие-то расположенные подряд блюда. Гости должны сесть так, чтобы не обидеть друг друга, то есть сумма стоимостей выбранных блюд должна у всех совпадать. И при этом не обидеть организаторов обеда, то есть съесть всё, что поставлено на стол.

Количество приглашённых всегда равно n, но некоторые приглашённые могут отсутствовать по уважительным причинам. Так что требуется для каждого количества пришедших на обед (от 1 до n включительно) определить, можно ли рассадить соответствующее число пришедших в соответствии с традицией.

В первой строке содержится натуральное число n — количество блюд на столе (1 ≤ n ≤ 105).

Во второй строке перечислена стоимость блюд ci в порядке обхода стола по часовой стрелке.

Стоимость — неотрицательное целое число, сумма всех стоимостей не превосходит бюджета компании (109 байтландских талеров).

4 1100
3 2 2 1

0