This page is still under construction.

Parts of this page are still being built. What you see may change.

Telescope

Time limit1sMemory limit256 MB

Summary
Count the 4-connected white regions of a binary sky given only its N by N averaged and rounded-down picture.
Level

Medium7 of 10

Topics
Greedy, Prefix sum, BFS
Solved
No attempts yet

Problem

The space telescope Inquisition IV was launched more than ten years ago, and the pictures it sends back are blurry. Each pixel of a picture is the average of the true pixels in the N×NN \times N square centred on that position, rounded down to an integer. NN is odd, so the square has exactly one centre. The average always divides by N2N^2, and a position of the square that falls outside the captured region counts as a black pixel.

The sky itself is simple. Every stellar body is a group of pixels of full brightness FFFF joined horizontally and vertically, and every other true pixel is fully black 0000. The telescope framed the whole scene, so no blur from a stellar body falls outside the picture. A pixel of brightness FFFF is therefore never within (N−1)/2(N-1)/2 rows or columns of the top, bottom, left or right border of the picture.

Read the blurred picture and count the stellar bodies in it.

Input

The first line has three integers NN, RR and CC (1≤N≤991 \le N \le 99, NN is odd, N≤R,C≤1000N \le R, C \le 1000): the side of the blur square, the number of rows of the picture and the number of columns of the picture.

Each of the next RR lines has CC hexadecimal numbers Lr,cL_{r,c} separated by one space. Every value is written with four uppercase hexadecimal digits and runs from 0000 (black) to FFFF (white). Lr,cL_{r,c} is the reported brightness of the pixel in row rr and column cc.

The given picture is always the blur of some sky that meets the rules above.

Output

Print one integer, the number of stellar bodies visible in the picture.

Examples2

  1. Example 1

    Input
    1 5 6
    0000 FFFF 0000 0000 0000 0000
    FFFF FFFF 0000 FFFF FFFF 0000
    0000 0000 0000 FFFF 0000 0000
    0000 FFFF FFFF FFFF FFFF 0000
    0000 0000 0000 0000 0000 0000
    
    Expected output
    2
    
  2. Example 2

    Input
    3 5 6
    1C71 1C71 1C71 0000 0000 0000
    1C71 1C71 1C71 0000 0000 0000
    1C71 1C71 1C71 1C71 1C71 1C71
    0000 0000 0000 1C71 1C71 1C71
    0000 0000 0000 1C71 1C71 1C71
    
    Expected output
    2