Card Divisibility

Time limit1sMemory limit1024 MB

Summary

Given consecutive integers from L to R, find the remainder when the number formed by writing them one after another is divided by 9.

Level: Medium4 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

For every pair of integers $a$ and $m$ with $m>0$ , there exist unique integers $q$ and $r$ such that $a=m⋅q+r$ and $0≤r\<m$ . This is a simple fact, but you wonder whether you can do something more interesting with this theory.

Right now, you are holding a handful of consecutive cards numbered from $L$ to $R$ . You lay the cards out side by side and concatenate their digits to form a single large number. You want the remainder when this number is divided by $9$ . For example, $L=9$ and $R=11$ means you hold cards 9, 10, and 11. Concatenating them produces 91011, and the remainder when it is divided by 9 is 3.

Input

A single line contains two integers $L$ ( $1≤L≤10^{12}$ ) and $R$ ( $L≤R≤10^{12}$ ). You hold the cards numbered from $L$ to $R$ , inclusive.

Output

Print a single line containing the remainder when the concatenated number is divided by $9$ .

Examples5

Example 1
Input
```
2 5
```
Expected output
```
5
```
Example 2
Input
```
3 10
```
Expected output
```
7
```
Example 3
Input
```
3 100
```
Expected output
```
7
```
Example 4
Input
```
1000000000 1000000007
```
Expected output
```
0
```
Example 5
Input
```
9 11
```
Expected output
```
3
```