아날로그 다이얼
시간 제한1초메모리 제한256 MB
숫자판 N개에 대해 구간 합을 구하고 그 구간의 숫자를 1씩 증가시키며 9는 0으로 넘어가는 연산을 M번 처리해 각 질의 시점의 구간 합을 출력합니다.
문제
아날로그 다이얼은 0부터 9까지의 숫자 중 하나를 표시하는 장치이다. 버튼을 누르면 표시된 숫자가 1 증가하고, 9에서 버튼을 누르면 0이 된다.
N개의 다이얼이 왼쪽부터 1번부터 N번까지 일렬로 놓여 있다. 처음에 각 다이얼이 표시하는 숫자가 주어진다. 이후 M번의 조작 기록이 주어진다. 각 조작은 두 정수 A와 B로 이루어지며, 실제 게임에서는 다음 순서로 진행되었다.
- 현재 A번째부터 B번째 다이얼에 표시된 숫자의 합을 기록한다.
- 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개의 줄에 걸쳐, 각 조작에서 버튼을 누르기 전에 기록된 구간 합을 순서대로 출력한다.