주차장 순환 점검 구간

문제

한 주차장의 주차 칸은 원형 통로를 따라 1번부터 N번까지 시계 방향으로 배치되어 있다. N번 칸 다음에는 다시 1번 칸이 나온다. 관리실은 야간 점검을 시작하기 직전에 각 칸에 차량이 있는지를 기록했다. 이 기록에서 문자 1은 차량이 있는 칸을, 문자 0은 비어 있는 칸을 뜻한다. 점검 중에는 차량이 들어오거나 나가지 않으므로 모든 질문은 같은 기록을 기준으로 처리한다. 점검 담당자는 출발 칸 L과 마지막 칸 R을 정하고, L번 칸부터 시계 방향으로 이동하면서 R번 칸까지 확인한다. 출발 칸과 마지막 칸도 확인 대상에 포함한다. L이 R보다 크면 N번 칸을 지난 뒤 1번 칸으로 돌아와 계속 이동한다. L과 R이 같으면 그 칸 하나만 확인하며, 주차장을 한 바퀴 도는 것으로 해석하지 않는다. 어떤 점검에서도 같은 칸을 두 번 확인하지 않는다. 예를 들어 8개의 칸이 있는 주차장에서 출발 칸이 7이고 마지막 칸이 2라면 7번, 8번, 1번, 2번 칸을 차례로 확인한다. 한편 출발 칸이 2이고 마지막 칸이 7이면 2번부터 7번까지의 칸만 확인한다. 따라서 두 번호의 대소 관계에 따라 실제 점검 구간이 달라질 수 있다. 관리실에는 서로 독립적인 Q개의 점검 질문이 도착했다. 각 질문에 대해 해당 구간에서 차량이 있는 칸의 수를 구해야 한다. 앞선 질문의 결과가 이후 질문의 구간이나 주차 상태에 영향을 주지는 않는다. 차량이 있는 칸이 하나도 없으면 그 질문의 답은 0이다. 질문이 주어진 순서대로 답을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 10,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어지며, 왼쪽부터 1번 칸부터 N번 칸까지의 상태다.
다음 Q개의 줄에는 정수 L과 R이 공백으로 주어진다. 1 ≤ L, R ≤ N이다.

출력

Q개의 줄에 걸쳐 각 질문의 답을 정수로 출력한다. 각 답은 0 이상 N 이하이다.

8 4
10110100
1 4
6 2
3 3
8 7

3
2
1
4

1 2
0
1 1
1 1

0
0

출처: Devin.KR 자체 제작