Apple Count

Time limit1sMemory limit128 MB

Summary

Given range [A,B] up to 10^15, sum for each number a value derived from run-length groups of equal digits, using digit-DP for efficiency.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

A village has apple trees standing in a row along its main street. The first tree is numbered 1, and the following trees are numbered in order.

For a tree numbered N, look at the decimal representation of N and split it into maximal consecutive groups of the same digit. If a group consists of digit d repeated L times, that group contributes d \times L^2 apples. The number of apples on the tree is the sum of these contributions over all groups.

Given two tree numbers A and B, compute the total number of apples on every tree from A through B, inclusive.

Input

The first line contains two integers A and B.

1 \le A \le B \le 10^{15}

Output

Print the total number of apples on trees numbered from A through B, including both endpoints.

Examples3

Example 1
Input
```
1 9
```
Expected output
```
45
```
Example 2
Input
```
100 111
```
Expected output
```
68
```
Example 3
Input
```
7774407 7774407
```
Expected output
```
86
```