You are given a closed interval `[a, b]`. You are to compute the sum of digits of all **odd** numbers in the interval.

### Input

The first line contains two integers: `a` and `b`.

### Output

The sum of digits of all the odd numbers between `a` and `b`, inclusive.

### Constraints

`1 ≤ a ≤ b ≤ 10`^{9}

### Sample

Input | Output | Explanation |
---|---|---|

1 5 | 9 | 1 + 3 + 5 = 9 |

5 27 | 75 | The odd number from the interval [5, 27] are: 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27. He have to compute: 5 + 7 + 9 + 1+1 + 1+3 + 1+5 + 1+7 + 1+9 + 2+1 + 2+3 + 2+5 + 2+7 = 75 |

# Solution by Gabriel-Robert Inelus

In order to solve the problem we have to compute the digit sum of all numbers in the closed interval `[0, x]`. For this, we need to precompute the digit sum, `sum[n]`, on closed intervals `[0, 99…9]` where `9` occurs `n` times.

Writing the first few terms of the sum on intervals `[0, 9]`, `[0, 99]`, `[0, 999]` we observe that the digit sum is: `sum[i] = i * 10 ^{i-1} * 45`.

Now, to get the digit sum of the numbers in the closed interval `[a, b]`, we firstly need to compute a function `F`, where `F(x)` is the digit sum on interval `[0, x]`. The first useful observation is that for a given digit `d` which appears on position `p` (right to left in the number, 1-indexed), the digit `sum[p-1]` appears exactly `d` times.

For the sake of an example, digit `5` in `89959914`, adds the sum `[0, 9999]` `5` times to the digit sum, also digit `8` adds `sum[7]` exactly `8` times. On a smaller example: `378`, digit `3` adds the sum `[0, 99]` 3 times: `0[0, 99]`, `1[0, 99]` and `2[0, 99]`.

The next useful observation is that a given digit `d` on position `p` (right to left, 1-indexed) contributes with `d*(d-1)/2 * 10 ^{p-1}` to the sum. For the sake of another example, digit

`3`of

`378`, contributes in this way:

`0 - 100`times,

`1 - 100`times, and

`2 - 100`times. This is

`100 * (3*2/2)`.

Currently, we took into consideration the `[0, 99…9]` sums (which look like suffixes of numbers), and the current digit. Now, we have to take into consideration the prefix of the number which also contributes to the sum. The digit sum of the prefix (without the current position `p`) will be repeated `d * 10 ^{p-1}` times. Thus, we need to know:

`nrdig`- the number of digits`prefix_sum[p]`- the prefix sum of the leftmost`p`digits`sum[n]`which is the digit sum on interval`[0, 999…9]`where`9`repeats`n`times`digit[k]`-`k`digit right to left^{th}

The final formula for `F(x)` is:

`Σ(digit[k]*sum[k-1] + digit[k]*(digit[k]-1)/2 * 10`.

^{k-1}+ prefix_sum[k+1] * digit[k] * 10^{k-1}) for k = nrdig to 1Note that the three terms of the sum corespond to the suffix contribution (all the `[0, 999…9]` digit sums), the current digit's contribution and the contribution of the current prefix. In the end, we have to add the digit sum of the actual number as we added everything up to the number `-1`.

Now that we have the function `F(x)` which returns the digit sum on any interval `[0, x]`, we have to use it in a smart way to obtain the digit sum on the interval `[a, b]`. So, the digit sum on interval `[a, b]` is `F(b) - F(a-1)` given that `a` is positive, otherwise it is simply `F(b)`.

We now have all the tools in order to solve the problem. The relation between the odd-number digit sum and the digit sum of all the numbers in interval `[a, b]` is pretty easy. First of all, we make the interval of the shape `[newA, newB]` such that `newA` is even and `newB` is odd, by adding `1` to `a` in case it is odd and subtracting `1` to `b` in case it is even. Now, for each odd number in the interval `[a, b]` there exists exactly one even number, whose digit sum is `1` less than the respective odd number. Thus, the digit sum of odd numbers in the adjusted interval is the digit sum of all numbers in the adjusted interval, plus the number of odd numbers (which is `(newB-newA+1)/2`), divided by two. In case the original `a` was odd and we increased it by one unit, we need to add `digitsum(original_a)` to the result.

Finally, the solution is: `(Interval_sum(a, b) + (b-a+1)/2)/2` and we add the digit sum of `(a-1)` in case it was originally an odd number and we added `1` to make it even. Note that here, `a` and `b` are the modified ones such that `a` is even and `b` is odd (so we always have a previous even number to all the odd ones - which has digit sum `1` less, as previously discussed) and `Interval_sum(a, b)` is `F(b) - F(a-1)` in case `a` is positive, otherwise if `a` is `0` the result is `F(b)`.