Случилось ужасное! Отважный хорватский охотник попал в его собственную ловушку. В погоне за ценной добычей он помчался вперед и оказался пойман. Чтобы выбраться наружу, он должен решить следующую задачу (а так как умом он не блещет, вам придется ему помочь):

Вам даны 3 целых числа L, D и X. Определите минимальное такое число N , для которого L ≤ N ≤ D и сумма цифр которого равна X . Также определите максимальное M для которого L ≤ M ≤ D и сумма цифр которого равна X . Гарантируется, что такие числа всегда существуют.

Ночью Мирко приснилась гистограмма из N столбиков. Каждый из них имел ширину в 1 метр, а высоты столбиков в метрах равны h ₁ , h ₂ , ... , h _N .

Вместимостью гистограммы называется максимальное количество воды (в квадратных метрах) которое она может удержать так, что конфигурация воды "стабильная", иными словами, вода в ней не перемещается под воздействием сил гравитации.

Формально, пусть количество воды над столбиками равно v ₁ , v ₂ , ... , v _N соответственно. Тогда конфигурация воды стабильна, если выполняются следующие условия:

1. h _i + v _i ≤ h _{i - 1} + v _{i - 1} для каждого i ≥ 2 , такого что v _i > 0 .

2. h _i + v _i ≤ h _{i + 1} + v _{i + 1} для каждого i ≤ N - 1 , такого что v _i > 0 .

3. v ₁ = 0 и v _N = 0 .

Проснувшись, Мирко захотел нарисовать такую гистограмму, чтобы высоты ее столбиков были перестановкой множества {1, 2, ... , N} и ее вместимость была в точности равна его счастливому числу X . Помогите Мирко и найдите такую гистограмму.

Юная Мирка - начинающий музыкант. Она играет на мульти-пианино. Мульти-пианино имеет бесконечно много мульти-клавиш, обозначенных целыми числами, которые можно воспринимать как ноты. Мульти-композиция (композиция для мульти-пианино) может быть представлено как последовательность чисел, обозначающих мульти-клавиши, которые должны быть нажаты (то есть ноты, которые должны быть сыграны).

Мирка услышала на мульти-радио мульти-композицию, и теперь она хочет сыграть ее. К сожалению, она не не умеет точно узнавать ноты по звуку, но может понимать, была ли нота с радио выше или ниже последней сыгранной ей ноты. Поэтому, она решила сыграть мульти-композицию следующим образом:

1. Перед началом игры, она выберет целое неотрицательное число K .

2. В начале, она сыграет правильную ноту (ее мульти-учитель сказал ей, какую клавишу нужно нажать первой)

3. Когда она услышит ноту выше, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K больше, чем она только что сыграла.

4. Когда она услышит ноту ниже, чем она только что сыграла, она будет нажимать на мульти-клавишу с числом на K меньше, чем она только что сыграла.

5. Когда она услышит такую же ноту, как только что сыграла, она будет нажимать на ту же мульти-клавишу, что только что сыграла.

Помогите Мирке выбрать такое K , чтобы она правильно сыграла как можно больше нот мульти-композиции.

Мирко и Славко играют в игру. Мирко ходит первым и выбирает непустое множество пар чисел от 1 до N (включительно). При этом числа в одной паре должны быть различны и взаимнопросты. Например, для N = 5 , Мирко может выбрать такое множество пар: {(1, 2), (3, 4), (2, 5), (3, 5)}.

Славко ходит вторым и его задача - найти разделяющий элемент для множества пар Мирко. Разделяющим элементом для множества пар называется такое число x из диапазона [2: N ] , что для каждой пары ( a , b ) из множества выполняется одно из двух условий:

1. a , b < x

2. a , b ≥ x

Например, множество пар {(1, 2), (3, 4)} имеет разделяющий элемент x = 3 .

Если разделяющий элемент существует, Славко обязательно его найдет, и тогда он выиграет. Мирко же выиграет, если Славко не сможет найти разделяющий элемент. Он просит вас помочь: определите, как много множеств пар, удовлетворяющих условию, он может выбрать, чтобы гарантированно выиграть. Так как это число может быть очень большим, выведите его по модулю 1 000 000 000.