회의실 사용 시간표

문제

한 건물의 회의실 관리자는 하루의 운영 시간을 길이가 같은 N개의 시간 칸으로 나누어 기록한다. 시간 칸에는 1번부터 N번까지 번호가 붙어 있다. 각 칸의 기록은 문자 0 또는 1이며, 0은 해당 칸에 회의실을 사용하지 않았다는 뜻이고 1은 사용했다는 뜻이다. 하나의 칸에서 회의가 몇 번 열렸는지나 몇 명이 참석했는지는 기록하지 않는다. 따라서 연속한 여러 칸에 1이 적혀 있어도 각 칸을 독립적으로 사용한 시간 한 칸으로 센다. 관리자는 이 기록으로 여러 보고서를 작성하려 한다. 각 보고서에는 조사할 구간의 첫 칸 L과 마지막 칸 R이 주어진다. 보고서에 적을 값은 L번부터 R번까지의 칸 중 사용 기록이 1인 칸의 개수다. 구간의 양 끝 칸도 조사 대상에 포함한다. 예를 들어 조사 구간 안의 기록이 10110이라면 사용한 시간은 세 칸이다. 구간 안에 사용한 칸이 하나도 없다면 보고서에 0을 적는다. 보고서 작성 요청은 모두 같은 하루의 기록을 대상으로 한다. 요청을 처리하는 동안 원래 기록은 바뀌지 않으며, 앞선 요청의 결과가 다음 요청에 영향을 주지도 않는다. 서로 같은 구간이 여러 번 요청될 수 있고, 서로 겹치는 구간이나 하루 전체를 대상으로 하는 구간도 주어질 수 있다. 조사 구간이 한 칸으로만 이루어진 경우에는 그 칸의 기록을 그대로 개수로 해석한다. 요청마다 구간을 다시 훑는 대신, 하루의 기록을 미리 정리하여 많은 요청에 답하려 한다. 주어진 순서대로 각 보고서에 들어갈 사용 시간 칸의 개수를 구하는 프로그램을 작성한다. 출력하는 수는 회의의 개수나 사용률이 아니라, 지정된 구간에서 사용한 시간 칸의 개수다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1 ≤ N ≤ 100,000이며 1 ≤ Q ≤ 10,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 0 또는 1이며, 왼쪽에서 i번째 문자가 i번 시간 칸의 기록이다.
다음 Q개의 줄에는 정수 L과 R이 주어진다. 1 ≤ L ≤ R ≤ N이다.

출력

각 요청에 대한 사용 시간 칸의 개수를 요청 순서대로 한 줄에 하나씩 출력한다. 사용한 칸이 없으면 0을 출력한다.

8 4
10110100
1 8
2 5
4 4
7 8

4
2
1
0

1 2
0
1 1
1 1

0
0

출처: Devin.KR 자체 제작