팩스 영역

팩스 이미지는 어두운 픽셀과 흰색 픽셀로 이루어진 직사각형 격자입니다. 어두운 픽셀들이 이루는 연결 요소(connected component)의 개수를 세는 것이 목표입니다.

두 어두운 픽셀은 가로 또는 세로로 바로 인접해 있을 때 같은 연결 요소에 속합니다. 모서리에서만 닿는(대각선으로 맞닿는) 픽셀끼리는 서로 연결된 것으로 보지 않습니다.

전송 대역폭을 아끼기 위해 팩스는 부호화된 형태로 보냅니다. 이미지의 첫 번째 행 위에 모두 흰색인 행이 하나 더 있다고 상상합니다. 픽셀을 행 우선 순서(한 행을 왼쪽에서 오른쪽으로 읽고, 이어서 그 아래 행으로 넘어가는 순서)로 훑으며 각 픽셀에 다음과 같이 표시합니다.

• S(same): 바로 위 픽셀과 색이 같으면
• D(different): 바로 위 픽셀과 색이 반대이면

예시로 든 세 개의 팩스를 행 우선 순서로 읽으면 다음과 같은 표시 문자열이 나옵니다.

• 팩스 1: SDDSDDSSSDDDSDD
• 팩스 2: DDDDDDDSSDDDDSSSDSDSSSDSSDSSSSSSDSSSSSSSSSSSSSDSSSDSDDDS
• 팩스 3: DSDSDSDS 뒤에 D 56개가 더 이어진 문자열(전체 64개)

이 표시 문자열은 항상 (비어 있을 수도 있는) S의 나열로 시작하고, 그 뒤로 S 나열과 D 나열이 번갈아 나타납니다. 각 나열의 길이를 순서대로 적되 언제나 S 나열의 개수부터 적으면(그 값이 0이라도) 다음과 같습니다.

• 팩스 1: 1 2 1 2 3 3 1 2
• 팩스 2: 0 7 2 4 3 1 1 1 3 1 2 1 6 1 13 1 3 1 1 3 1
• 팩스 3: 0 1 1 1 1 1 1 1 1 56

이 나열 길이 목록과 이미지의 너비가 곧 부호화 결과입니다. 각 팩스의 너비와 부호화 결과가 주어질 때, 어두운 픽셀이 이루는 연결 요소의 개수를 출력하세요. 위 예시에서 팩스 1은 2개, 팩스 2는 3개, 팩스 3은 32개의 연결 요소를 가집니다(팩스 3의 어두운 픽셀 32개는 모두 모서리에서만 닿으므로 각각이 하나의 연결 요소입니다).

팩스는 매우 클 수 있으므로, 모든 픽셀을 하나하나 살펴보는 방법은 너무 느립니다.

입력은 1개 이상 24개 이하의 데이터 집합으로 이루어지며, 마지막에는 -1만 있는 줄이 옵니다.

각 데이터 집합은 세 개의 양의 정수 w, r, g가 있는 줄로 시작합니다.

• w — 팩스의 너비(픽셀 수), $w \le 10^9$
• r — 부호화에 들어 있는 나열 길이의 총개수, $r \le 1000$
• g — 한 줄에 적히는 나열 길이의 개수, $g \le 40$

그다음 r개의 나열 길이가 한 줄에 g개씩 주어집니다(마지막 줄은 g개보다 적을 수 있습니다). 한 줄의 수들은 공백으로 구분됩니다. 첫 번째 나열 길이는 0일 수 있고, 나머지는 모두 양수이며 어떤 나열 길이도 $10^9$을 넘지 않습니다.

각 팩스의 전체 픽셀 수(모든 나열 길이의 합)는 w의 배수이므로 픽셀은 항상 완전한 직사각형을 이룹니다. 입력의 정수에는 쉼표가 들어 있지 않습니다.

각 데이터 집합마다 한 줄에 정수 하나, 곧 그 팩스에서 어두운 픽셀이 이루는 연결 요소의 개수를 출력하세요. 입력의 어떤 팩스도 연결 요소가 $10^9$개를 넘지 않습니다.