This page is still under construction.

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

Advertising Billboard

Interview

Time limit2sMemory limit512 MB

Summary
Given k on/off patterns for an n by m grid of bulbs, partition the bulbs into the fewest groups so that within each pattern every group is uniformly on or uniformly off.
Level

Medium6 of 10

Topics
Union-find, Implementation, Hash map, Brute force
Solved
No attempts yet

Problem

To advertise its new products in China, a company decided to put an advertising billboard on a skyscraper. The billboard consists of light bulbs arranged in a rectangular grid of nn rows and mm columns. At any moment each bulb is either on or off.

The advertising message consists of kk characters, which are shown one after another. For each character, the bulbs that must be on while that character is displayed are known. The remaining bulbs must be off.

A special system is being developed to control the billboard. The system can turn bulbs on and off in whole groups. All bulbs are split into several groups so that, in each character, the bulbs of one group must be either all on or all off.

To optimize the operation of the control system, the bulbs must be split into the smallest possible number of such groups. Help the employees of the company's advertising department solve this problem.

Input

The first line of the input file contains the numbers kk, nn, and mm (1≤k,n,m≤1001 \le k, n, m \le 100), which are the number of characters in the advertising message, the height, and the width of the billboard.

Then knkn lines describe the characters. Each of the kk characters is given by nn lines of mm characters each. All these lines consist only of the characters <<*>> and <<.>>, where <<*>> corresponds to a bulb that is on and <<.>> to a bulb that is off.

Output

Print the minimum number of groups into which the bulbs can be split.

Hint

In the given example, the bulbs can be split into groups as follows: the two bulbs in the first column form one group, the two bulbs in the last column form the second, and each of the two remaining bulbs forms a separate group.

Examples1

  1. Example 1

    Input
    3 2 3
    *..
    *..
    **.
    *..
    ...
    .*.
    
    Expected output
    4