Dream Counting

Time limit1sMemory limit128 MB

Summary

Count how many times each decimal digit 0 through 9 appears when writing every integer from M to N.

Level: Medium5 of 10
Topics: Math, Brute force, Implementation, Number theory
Solved: No attempts yet

Problem

Bessie the cow was daydreaming, drifting between wakefulness and that pleasant drowsiness we all feel when we are tired. Unable to fall asleep, she counted numbers instead of sheep. Bessie's mind is razor sharp, so as she counts she pictures every number vividly and starts noticing its digits. She wonders: while counting through a run of consecutive integers, how many times does each digit appear?

Given two integers $M$ and $N$ , consider every integer from $M$ to $N$ inclusive. For each digit from $0$ to $9$ , count how many times that digit appears across the decimal representations of all of these numbers.

Constraints:

$1 \le M \le N \le 2{,}000{,}000{,}000$
$N - M \le 500{,}000$

Input

Line 1: Two space-separated integers, $M$ and $N$ .

Output

Line 1: Ten space-separated integers. The $i$ -th integer (for $i$ from $0$ to $9$ ) is the number of times digit $i$ appears while writing out every integer from $M$ to $N$ .

Examples2

Example 1
Input
```
129 137
```
Expected output
```
1 10 2 9 1 1 1 1 0 1
```
Example 2
Input
```
1 10
```
Expected output
```
1 2 1 1 1 1 1 1 1 1
```