Since you have learned Modular Arithmetic, you know how to
work with quotients and remainders. For every pair of integers
$a$ and $m$ with $m>0$, there exist unique integers
$q$ and $r$ such that $a = m\cdot q+r$ and $0 \leq r < m$. But this is a bit
simple, you wonder if 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 to create a single large number (i.e.
concatenating the digits of your cards). You would like to know
the remainder (which is the $r$ in $a = m\cdot q + r$) when this number
is divided by $9$. For
example, $L = 9$ and
$R = 11$ means you are
holding cards $9, 10, 11$.
Concatenating these numbers produces the number $91011$. The remainder $r$ left upon dividing this number by
$9$ would be $r = 3$.
Input
Input consists of a single line containing two integers
$L$ ($1 \leq L \leq 10^{12}$) and
$R$ ($L \leq R \leq 10^{12}$). This means
you are holding the cards with numbers from $L$ to $R$, inclusive.
Output
Display a single line containing the remainder of the
concatenated number if you were to divide it by $9$.
| Sample Input 1 |
Sample Output 1 |
2 5
|
5
|
| Sample Input 2 |
Sample Output 2 |
3 10
|
7
|
| Sample Input 3 |
Sample Output 3 |
3 100
|
7
|
| Sample Input 4 |
Sample Output 4 |
1000000000 1000000007
|
0
|
| Sample Input 5 |
Sample Output 5 |
9 11
|
3
|
