Description

On the planet Sanuel, scientific exploration is carried out by an intelligent rover named Smart. Because Sanuel is far from Earth, a round-trip signal transmission takes several hours and has a high error rate. Therefore, scientists cannot control the Smart rover in real time from Earth. Most exploration tasks are autonomously completed by the rover through analyzing environmental factors and making independent decisions.

The rover’s design is relatively simple:

First, list the various decision factors that affect the rover’s actions, such as weather, landform, energy (power supply), and mine (number of collected ores).

Next, divide each decision factor into two primary situations. For example, divide weather into sunny and windy; divide the rover’s energy into full and lack, etc.

Then, for each action, scientists list all decision conditions according to the decision factors. For example, suppose the decision factors that affect ore collection have $N=4$ types, and the decision conditions for collecting ore are as follows:

There are many actions and many corresponding decision conditions. To improve decision speed, the intelligent induction module on the rover needs to summarize all decision conditions of each action into a single “decision template.”

For example, the above decision conditions for ore collection can be summarized as:

Here, “*” means that the factor does not affect the action decision of the rover.

Obviously, the decision template must cover all listed decision conditions for that action. Meanwhile, the decision template will also include some decision conditions that scientists did not list, so the rover can act automatically under unlisted decision conditions, showing some degree of “intelligence.” For example, the above decision template will cause the rover to collect ore under the following decision condition as well.

However, everything has two sides. If the decision template is too general, it loses its decision value and becomes imprecise. For example, the following decision template, although it covers all the listed ore collection decision conditions, is too general to be meaningful.

Therefore, the number of “*” used in the decision template should be as few as possible.

Xiao Keke (pinyin) is in charge of developing the rover’s intelligent induction module. Please write a program to help Xiao Keke complete this task.

Input Format

The first line contains two positive integers $N$ and $M$ separated by a space, representing the number of decision factors ($N \leq 100$) and the number of decision conditions for a certain action ($M \leq 1000$).

Each of the next $M$ lines is a string consisting of $N$ words. Each word corresponds, in order, to the situation of one decision factor, and each line represents one decision condition. Words on each line are separated by a single space.

Note: There are no extra whitespace characters at the beginning or end of any line. Words consist only of lowercase English letters and have a length of at most 10.

Output Format

Output a single line representing the decision template, consisting of $N$ words or “*”, separated by single spaces. There should be no extra whitespace at the beginning or end of the line.

4 3
sunny plain full many
sunny mountain full many
sunny mountain full few

sunny * full *

Hint

Translated by ChatGPT 5