Рассмотрим произвольную последовательность целых чисел. Между числами можно расставить знаки арифметических операций + или – , и таким образом получать некоторые выражения, которые принимают различные значения. Например, если взять последовательность: 17, 5,  - 21, 15, то можно получить восемь различных выражений:

Назовем последовательность делящейся на натуральное K, если + и – могут быть расставлены так, что итоговое значение выражения будет делиться на K. В приведенном примере последовательность делится на 7  (17 + 5 +  - 21 - 15 =  - 14), но не делится на 5.

Ваша задача — написать программу, определяющую делимость последовательности на целое число.

Андрей Сергеевич работает воспитателем в детском саду. Недавно он придумал новую веселую игру, для участия в которой все дети разбились на n команд. В качестве призов для участников игры Андрей Сергеевич подготовил d конфет.

По итогам игры оказалось, что в команде, занявшей i -е место, ровно x _i участников.

Теперь перед Андреем Сергеевичем стоит непростая задача: надо распределить конфеты. При этом должны выполняться следующие условия:

• Все участники одной команды должны получить поровну конфет: пусть участники команды, занявшей i -е место получат по a _i конфет;
• Каждый ребенок должен получить хотя бы одну конфету: a _i > 0 ;
• Участники команды, занявшей более высокое место, должны получить больше конфет: если i < j , то a _i > a _j
• Все конфеты должны быть распределены: a _{1 x 1} + a _{2 x 2} + ... a _{nx n} = d

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4 ^{n - 1} грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c _i , время его завоза в магазин a _i и время его вывоза из магазина b _i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m _j , время s _j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k _j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k _j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.