[문제 요약] 3 번째 입출력 예로 설명 하면

7 5 ... 7 개의 수 시행횟수 5 
9081337  ... 초기 배치 
1 3 
3 7 
1 3 
3 7 
1 3 

• 1 번째 수에서 3 번째 수의 합은 : 9 + 0 + 8 = 17
• 1 번째 수에서 3 번째의 수를 1 증가( 9 이면 0 으로 ) -> 0 1 9 1 3 3 7
• 3 번째 7 번째 수의 합: 9 + 1 + 3 + 3 + 7 = 23
• 3 번째 7 번째 수를 1 증가 -> 0 1 0 2 4 4 8
• 1 번째 3 번째 수의 합 : 0 + 1 + 0 = 1
• 1 번째 3 번째 수를 1 증가 -> 1 2 1 2 4 4 8
• ..

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:

• Choose two integers A and B (1 ≤ A ≤ B ≤ N) and write them down on the first sheet.
• Calculate the sum of numbers on dials numbered between A and B (inclusive), and write the sum down on the second sheet.
• Press the button once on all dials numbered between A and B.

Given the contents of the first sheet, help him calculate the numbers on the second sheet.

입력

• The first line 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).

출력

입출력 예

input 

4 3 
1234 
1 4 
1 4 
1 4 

output 

10 
14 
18 

input 

4 4 
1234 
1 1 
1 2 
1 3 
1 4 

output 

1 
4 
9 
16

input 

7 5 
9081337 
1 3 
3 7 
1 3 
3 7 
1 3 

output 

17 
23 
1 
19 
5 

출처:coci 2007-2008 contest3 6/6