주차선 사이의 점검등

문제

한 주차장에는 주차 칸 N개가 일렬로 놓여 있다. 주차 칸에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, 각 칸에는 차량이 없거나 정확히 한 대가 있다. 관리자는 나란히 주차된 차량 사이를 점검하기 위해 서로 이웃한 두 주차 칸 사이마다 점검등을 하나씩 설치했다. i번 점검등은 i번 칸과 i+1번 칸 사이에 있으며, 두 칸에 모두 차량이 있을 때에만 켜진다. 주차장은 원형이 아니므로 1번 칸과 N번 칸 사이에는 점검등이 없다. 주차 칸이 하나뿐이면 점검등도 하나도 없다. 연속한 세 칸에 모두 차량이 있으면 그 사이의 점검등 두 개가 각각 켜진다. 따라서 차량 한 대가 양쪽의 서로 다른 점검등을 켜는 데 동시에 관여할 수 있다. 점검등은 차량의 종류나 주차 시간과 관계없이 현재 두 칸의 상태로만 결정된다. 주차장 관제 장치는 상태 변경 기록을 차례대로 전달한다. 기록 하나에는 주차 칸 번호 X가 들어 있다. 이 기록을 처리하면 X번 칸의 상태를 반대로 바꾼다. 차량이 없던 칸에는 차량이 한 대 들어오고, 차량이 있던 칸에서는 그 차량이 나간다. 다른 칸의 상태는 바뀌지 않는다. 변경 직후 모든 점검등은 새 주차 상태에 맞추어 켜지거나 꺼진다. 같은 번호가 여러 번 연속해서 기록될 수도 있으며, 그때도 매 기록마다 상태를 한 번씩 바꾼다. 각 기록은 바로 앞 기록까지 모두 처리한 상태에 적용한다. 초기 주차 상태에 대한 점검등 수는 출력하지 않고, 기록을 하나 처리할 때마다 그 직후 켜져 있는 점검등의 전체 개수를 출력한다. 초기 상태와 Q개의 변경 기록이 주어진다. 모든 기록에 대해 켜진 점검등 수를 순서대로 구한다. 양쪽 칸에 차량이 있는 점검등이 하나도 없다면 해당 기록의 답은 0이다.

입력

첫째 줄에 주차 칸 수 N과 기록 수 Q가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고, Q는 1 이상 40,000 이하의 정수다.
둘째 줄에 길이가 N인 문자열이 주어진다. 각 문자는 0 또는 1이며, i번째 문자가 0이면 i번 칸이 비어 있고 1이면 차량이 있다.
다음 Q개 줄에 상태를 바꿀 주차 칸 번호 X가 하나씩 주어진다. X는 1 이상 N 이하의 정수다.

출력

Q개 줄에 답을 출력한다. j번째 줄에는 j번째 변경 기록을 처리한 직후 켜진 점검등의 전체 개수를 정수로 출력한다.

5 4
11010
3
2
5
1

3
1
2
2

1 3
0
1
1
1

0
0
0

출처: Devin.KR 자체 제작