Задача 05. Треугольник ≡

Условие

Валерий Брюсов, "Треугольник", 1918 г.

"Всё-таки поздний Брюсов с одной стороны — молодец, вон "Краткий курс науки о стихе" написал. Привёл примеры на все существующие размеры, ритмы, рифмы, строфы, работал в редких жанрах, таких как рубаи, сапфические строфы и даже стихи в форме треугольника. Зато с другой — в них нет ни капли поэзии. Какой-то аппарат для деланья стихов",  — печально размышляет Тимофей.

То ли дело — математические треугольники! Какая мощь в треугольнике Паскаля! Какая красота в треугольнике Серпинского! А невозможный треугольник Пенроуза! Нет, нужно работать в этом направлении.

В результате получасовых размышлений, Тимофей описал правила построения треугольника Тимофея.

1) В его первой строке единственная цифра 0.

2) Каждая следующая строка начинается с цифры, с которой начинается предыдущая строка, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая строка начинается с 9, то следующая начнётся с 0).

3) Каждая следующая цифра строки равна предыдущей цифре, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая цифра — 9, то следующая — 0).

4) В каждой новой строке на 2 цифры больше, чем в предыдущей.

На рисунке ниже вы можете видеть треугольник Тимофея с первыми 7 строками.

Теперь Тимофей хочет узнать, сколько цифр каждого вида находится в треугольнике с первыми n строками.

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите через пробел десять чисел — количество цифр от 0 до 9 в треугольнике.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10³, получат не менее 30 баллов.

Решения, верно работающие при n ≤ 10⁵, получат не менее 60 баллов.

Пояснение к примеру

Смотри рисунок.

Примеры тестов

7

4 4 5 5 5 6 6 5 5 4