Page Numbering

Time limit1sMemory limit1024 MB

Summary

Count how many times each digit 0-9 appears in all odd page numbers from 1 up to N, with N as large as 10^12.

Level: Medium7 of 10
Topics: Math, Implementation, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

A book has $N$ pages, and the publisher wants to save money by printing page numbers only on the right-hand pages, that is, the odd numbers. Write a program that counts how many times each digit is used.

Input

A single line with the integer $N$ .

Output

Print $10$ integers on one line: the number of times each digit is used. First the number of zeros, then the number of ones, and so on.

Constraints

$1 \le N \le 10^{12}$

Examples3

Example 1
Input
```
23
```
Expected output
```
0 8 2 3 0 2 0 2 0 2
```
Example 2
Input
```
306
```
Expected output
```
13 96 65 49 15 46 15 45 15 45
```

Example 3

Input

Expected output

12178 25911 17233 25411 17205 25409 17200 25405 13228 20405