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

Вам даны 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 . Помогите Мирко и найдите такую гистограмму.