아날로그 다이얼

아날로그 다이얼은 0부터 9까지의 숫자 중 하나를 표시하는 장치이다. 버튼을 누르면 표시된 숫자가 1 증가하고, 9에서 버튼을 누르면 0이 된다.

N개의 다이얼이 왼쪽부터 1번부터 N번까지 일렬로 놓여 있다. 처음에 각 다이얼이 표시하는 숫자가 주어진다. 이후 M번의 조작 기록이 주어진다. 각 조작은 두 정수 A와 B로 이루어지며, 실제 게임에서는 다음 순서로 진행되었다.

1. 현재 A번째부터 B번째 다이얼에 표시된 숫자의 합을 기록한다.
2. A번째부터 B번째까지 모든 다이얼의 버튼을 한 번씩 눌러 각 숫자를 1 증가시킨다. 이때 9는 0으로 바뀐다.

초기 숫자와 M개의 구간 기록만 알고 있을 때, 각 조작에서 기록된 구간 합을 순서대로 구하시오.

첫째 줄에 두 정수 N과 M이 주어진다. (1 <= N <= 250,000, 1 <= M <= 100,000)

둘째 줄에는 처음에 다이얼에 표시된 N자리 숫자열이 공백 없이 주어진다.

다음 M개 줄에는 각 조작에서 고른 두 정수 A와 B가 주어진다. (1 <= A <= B <= N)

총 M개의 줄에 걸쳐, 각 조작에서 버튼을 누르기 전에 기록된 구간 합을 순서대로 출력한다.