CPCRC1C - Sum of Digits


Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.

Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.

Majid did finally find the solution. Now it is your turn, can you find a solution?

Input

Two space-separated integers 0 <= a <= b <= 109.

Program terminates if a and b are -1.

Output

The sum of the digits of numbers a through b.

Example

Input:
1 10
100 777
-1 -1

Output:
46
8655

hide comments
abhishen99: 2020-12-24 13:10:13

easy peasy ...

coder_619: 2020-09-15 13:12:55

3Dp Problem With State As: (pos,sum,tight)

ankit_code2799: 2020-05-28 20:42:08

AC in one go!

scolar_fuad: 2019-11-22 16:39:02

Basic Digit dp problem
Happy coding

bhagirathi08: 2019-09-08 05:59:12

Well got my first digit dp problem accepted, Thanks for the question. DIGIT DP works like a bliss!

mithun_rahman: 2019-07-11 18:34:08

it can be tagged as combinatorics

cicipi: 2018-06-19 15:27:14

just same as this one .....here b<=1e15
http://www.spoj.com/problems/PR003004/

codefield: 2018-05-18 11:38:45

can be solved without digit dp

Last edit: 2018-05-18 11:48:58
r19: 2018-02-26 20:59:51

A comment was left

Akshay Aradhya: 2018-02-04 12:56:06

Digit DP :)


Added by:Tii
Date:2010-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://cs.ikiu.ac.ir/cms/icpc/training/7-contest/86-contest1