Counting Digits

Time limit1sMemory limit128 MB

Summary

For each query range [A, B], count how many times each decimal digit 0 through 9 appears in all integers written out from A to B.

Level: Medium6 of 10
Topics: Math, Implementation, Combinatorics, Brute force
Solved: No attempts yet

Problem

Write a program that counts how many times each digit from $0$ to $9$ appears when every integer from $A$ to $B$ (inclusive) is written down in order.

Input

The input consists of several test cases. Each test case is a single line containing two integers $A$ and $B$ separated by a space. ( $1 \le A \le B \le 10^8$ )

The last line of the input contains two zeros; this line is not processed.

Output

For each test case, print $10$ integers on one line, separated by spaces. The $i$ -th integer is the number of times the digit $i-1$ appears when all numbers from $A$ to $B$ are written, printed in order from $0$ to $9$ .

Examples4

Example 1

Input

1 9
12 321
5987 6123
12345678 12345679
0 0

Expected output

0 1 1 1 1 1 1 1 1 1
61 169 163 83 61 61 61 61 61 61
134 58 28 24 23 36 147 24 27 47
0 2 2 2 2 2 2 2 1 1

Example 2
Input
```
1 1
0 0
```
Expected output
```
0 1 0 0 0 0 0 0 0 0
```
Example 3
Input
```
1 10
0 0
```
Expected output
```
1 2 1 1 1 1 1 1 1 1
```

Example 4

Input

10 10
99 100
0 0

Expected output

1 1 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 2