Description

Lana lives in a happy little village. Along the main street there is a row of cherry trees. Lana noticed that each tree is numbered with consecutive integers starting from $1$. After a lot of research, Lana discovered that a tree’s number uniquely determines how many cherries it has. For a given tree, split its number into groups of consecutive identical digits. For each group, multiply the unique digit in that group by the square of the group’s length. Add these values together to get the total number of cherries on the tree. For example, for the tree numbered $77744007$, we split the number into $4$ groups: $777$, $44$, $00$, and $7$. Therefore, the number of cherries on the tree numbered $77744007$ is $7\times 3^2+4\times 2^2+0\times2^2+7\times1^2=86$.

It is time to pick cherries. The villagers agreed to pick all cherries from the trees whose numbers are in the interval $[a,b]$. Now you need to write a program to compute the total number of cherries that will be picked.

Input Format

The input contains only one line with two integers $a,b$, representing the starting and ending tree numbers that can be picked.

Output Format

Output only one line with one integer, representing the total number of cherries that can be picked.

1 9

45

100 111

68

7774407 7774407

86

Hint

Constraints

For all testdata, $1\leqslant a\leqslant b\leqslant 10^{15}$.

Source

This problem is from COCI 2008-2009 CONTEST 5 T5 TRESNJA, using the original testdata configuration, with a full score of $120$ points.

Translated and整理 (zhengli) provided by Eason_AC.

Translated by ChatGPT 5