RiseOJ – Redoks

설명

선생님이 산화·환원 반응을 설명하는 동안 Luka는 또 수업에 집중하지 않고 있다. 집중하는 대신 아날로그 다이얼을 가지고 놀고 있다.

아날로그 다이얼은 항상 $$0$$ 이상 $$9$$ 이하의 숫자 하나를 표시하는 작은 장치이다. 장치에는 숫자를 $$1$$ 증가시키는 작은 버튼도 있다( $$9$$ 인 경우에는 $$0$$ 으로 바뀐다).

Luka의 책상에는 이런 다이얼이 $$N$$ 개 있는데, 왼쪽부터 오른쪽으로 $$1$$ 부터 $$N$$ 까지 번호가 붙어 있다. 그리고 그가 쓸 종이 두 장이 있다.

Luka의 게임은 다이얼들을 어떤 시작 상태로 맞춰 놓고, 그 상태를 첫 번째 종이에 적는 것으로 시작한다. 그런 다음 Luka는 다음을 $$M$$ 번 반복한다:

게임을 막 끝냈을 때 선생님이 그를 발견하고, 다이얼 전부와 두 번째 종이를 압수해 버렸다.

첫 번째 종이의 내용이 주어졌을 때, 두 번째 종이에 적힌 수들을 계산하도록 도와주자.

제약

입력 형식

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

둘째 줄에 다이얼들의 초기 상태가 공백 없이 $$N$$ 개의 십진 숫자로 주어진다. 첫 번째 숫자는 다이얼 $$1$$ 에 처음 표시된 수, 두 번째 숫자는 다이얼 $$2$$ 에 표시된 수, 이런 식이다.

다음 $$M$$ 개의 줄에는 두 정수 $$A$$ 와 $$B$$ ( $1 \le A \le B \le N$ )가 주어진다.

출력 형식

$$M$$ 개의 줄에 Luka가 계산한 합을 계산한 순서대로 출력한다.

채점: 전체 테스트 케이스의 $30\%$ 에서는 $$N$$ 과 $$M$$ 이 $$1000$$ 보다 작다.

서브태스크

서브태스크	점수	설명
Subtask 1	90점

예제 1

입력

출력

10
14
18

예제 2

입력

출력

예제 3

입력

출력

문제 정보

riseoj 작성

출처 COCI 2007/2008 Contest 3

태그

#자료 구조 JudgeCOCI

Redoks