Задача D. Цифровой прямоугольник

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

Условие

Тимофей заполнил прямоугольную таблицу размером n × m следующим образом: в левую верхнюю ячейку записал цифру d, в ячейку правее — цифру d + 1, в следующую — цифру d + 2 и так далее. Если на каком-то шаге ему нужно было записать число 10, вместо нее он записывал одну цифру 0.

Числа в остальных строках он заполнил следующим образом: каждое число в ячейке равнялось числу в ячейке выше, увеличенному на 1. Опять же, вместо 10 он записывал 0.

На рисунке ниже Вы видите заполненный цифровой прямоугольник при n = 5, m = 12 и d = 3.

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

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

Первые две строки входного файла содержит два натуральных числа: n и m — размеры таблицы. В третьей строке содержится десятичная цифра d, расположенная в левой верхней ячейке цифрового прямоугольника.

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

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

Ограничения

1 ≤ n, m ≤ 109

0 ≤ d ≤ 9

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

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

Решения, верно работающие при n = m = 1, получат не менее 5 баллов.

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

Решения, верно работающие при n = 1, получат не менее 20 баллов.

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

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

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

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

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

0.143s 0.021s 17