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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Валерий Брюсов, "Треугольник", 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 ≤ 109

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
7
4 4 5 5 5 6 6 5 5 4

0.140s 0.016s 19