Fax Regions

A fax image is a rectangular grid of dark and white pixels. Your task is to count the connected components formed by the dark pixels.

Two dark pixels belong to the same component when they are directly adjacent horizontally or vertically. Pixels that touch only at a corner (diagonally) are not connected.

To save transmission bandwidth, a fax is sent in an encoded form. Imagine an extra, all-white row placed above the first row of the image. Read the pixels in row-major order (left to right across a row, then continue on the next row down), and label each pixel:

• S (same) if it has the same color as the pixel directly above it, or
• D (different) if it has the opposite color.

For three example faxes, reading the labels in row-major order gives these strings:

• Fax 1: SDDSDDSSSDDDSDD
• Fax 2: DDDDDDDSSDDDDSSSDSDSSSDSSDSSSSSSDSSSSSSSSSSSSSDSSSDSDDDS
• Fax 3: DSDSDSDS followed by 56 more Ds (64 labels in all)

The label string always begins with a run of Ss (which may be empty), after which runs of S and D strictly alternate. Recording the length of each run in order — always starting with the S-run count, even when it is 0 — yields:

• Fax 1: 1 2 1 2 3 3 1 2
• Fax 2: 0 7 2 4 3 1 1 1 3 1 2 1 6 1 13 1 3 1 1 3 1
• Fax 3: 0 1 1 1 1 1 1 1 1 56

This list of run lengths, together with the image width, is the encoding. Given the width and the encoding of each fax, output the number of connected dark components. In these examples Fax 1 has 2 components, Fax 2 has 3, and Fax 3 has 32 (its 32 dark pixels touch only at corners, so each one is its own component).

The faxes may be extremely large, so an approach that inspects every pixel individually is far too slow.

The input contains from 1 to 24 data sets, followed by a final line containing only -1.

Each data set begins with a line holding three positive integers w, r, and g:

• w — the width of the fax in pixels, $w \le 10^9$
• r — the total number of run lengths in the encoding, $r \le 1000$
• g — how many run lengths are written per line, $g \le 40$

The r run lengths follow, g per line (the last line may contain fewer than g of them); numbers on a line are separated by blanks. The first run length may be 0; every other run length is positive, and no run length exceeds $10^9$.

The total number of pixels in each fax — the sum of all run lengths — is a multiple of w, so the pixels always form a complete rectangle. The integers in the input contain no commas.

For each data set, print one line containing a single integer: the number of connected dark components in that fax. No fax in the input has more than $10^9$ components.