Luka is not paying attention in class again, while the teacher is explaining redox reactions. Instead of
paying attention, he is playing with analog dials.
An analog dial is a small device which always shows one digit between 0 and 9. It also contains a small
button which increases the number by 1 (unless it is 9, in which case it is changed to 0).
Luka has N such dials on his desk, numbered 1 to N left to right, and two sheets of paper for him to
write on.
Luka's game starts with him setting the dials in some starting configuration, which he then writes onto
the first sheet. Luka then does the following M times:
Given the contents of the first sheet, help him calculate the numbers on the second sheet.
There are multiple test cases in the input file. Input is terminated by EOF.
The first line of each test case contains two integers N and M (1 ≤ N ≤ 250000, 1 ≤ M ≤ 100000).
The second line contains the initial configuration of the dials, N decimal digits with no spaces. The first
digit is the number initially on dial 1, the second digit the number on dial 2 and so on.
Each of the following M lines contains two integers A and B (1 ≤ A ≤ B ≤ N).
For each test case, output M lines, the sums calculated by Luka, in order in which he calculated them.
4 3 1234 1 4 1 4 1 4 4 4 1234 1 1 1 2 1 3 1 4 7 5 9081337 1 3 3 7 1 3 3 7 1 3
10 14 18 1 4 9 16 17 23 1 19 5
Migrated from old NTUJ.
COCI 2007/2008, contest 3
| No. | Testdata Range | Score |
|---|