Image Segmentation

You have joined a medical imaging company. Your task is to build a test program for an image-analysis system. Many devices, such as X-ray machines and ultrasound scanners, produce pictures of structures inside the human body. A first step in analysing such images automatically is to separate the image into connected regions of similar appearance or colour.

The meaning of connected is easiest to explain with a small artificial example. Consider the magnified image of 6 rows by 10 columns shown on the left below. It uses three pixel colours: white, grey and black. Two pixels of the same colour belong to the same region if they are adjacent horizontally, vertically or diagonally. So the 7 grey pixels form a single connected region. Altogether this image contains 5 connected regions. On the right, pixels in the same region share the same number.

Write a program that examines an image and reports the number of regions. A few extra rules apply:

• Images are in colour. Each pixel colour is a triple $(R, G, B)$ where $R$, $G$ and $B$ are integers from 0 to 255 inclusive.
• Real images rarely contain regions of exactly one colour, so similar colours must be treated as identical through banding. Each image comes with a band size $S$. Every colour value is converted to a band number by integer division by $S$: with $S = 32$, values $0..31$ map to band 0, $32..63$ map to band 1, and so on. For example the colour $(5, 32, 76)$ becomes the band triple $(0, 1, 2)$. Two colours are considered identical when their band triples are equal.
• For medical use, small regions may be ignored. Each image comes with a size limit $L$; do not count any region containing fewer than $L$ pixels.

The input is a sequence of images. Each image begins with a line of four space-separated integers $H\ W\ S\ L$ — the image height, image width, band size and region-size limit. Both $W$ and $H$ are in the range 1 to 1024 inclusive. This line is followed by $H$ lines of pixel data. Each such line holds $W$ triples giving the $R$, $G$ and $B$ values of successive pixels, with single spaces between numbers. The input ends with a line containing four zeros.

For each image, output a single line containing the number of regions in that image, not counting regions that are too small.