Analog Dial

Time limit1sMemory limit256 MB

Summary

Simulate M range-sum queries followed by range +1-with-wraparound-to-0 updates on N digit dials, using a data structure that supports both efficiently.

Level: Medium6 of 10
Topics: Segment tree, Prefix sum, Simulation
Solved: No attempts yet

Problem

An analog dial is a device that always displays one digit from 0 through 9. Pressing its button increases the displayed digit by 1, and pressing it while it shows 9 changes it to 0.

There are N dials placed in a row from left to right, numbered 1 through N. The initial digit displayed by each dial is given. Then M operation records are given. Each operation consists of two integers A and B, and the actual game proceeded in this order.

Record the sum of the digits currently displayed on dials A through B.
Press the button once on every dial from A through B, increasing each digit by 1. A digit 9 becomes 0.

Given only the initial digits and the M recorded intervals, output the range sum recorded during each operation, in order.

Input

The first line contains two integers N and M. (1 <= N <= 250,000, 1 <= M <= 100,000)

The second line contains the initial N-digit string displayed on the dials, without spaces.

Each of the next M lines contains two integers A and B chosen for one operation. (1 <= A <= B <= N)

Output

Print M lines. On each line, print the range sum recorded before pressing the buttons for the corresponding operation.

Examples3

Example 1
Input
```
4 3
1234
1 4
1 4
1 4
```
Expected output
```
10
14
18
```
Example 2
Input
```
4 4
1234
1 1
1 2
1 3
1 4
```
Expected output
```
1
4
9
16
```

Example 3

Input

Expected output