Minimal Wildcard Decision Template

On planet Sanuel, the scientific expeditions are carried out by an intelligent rover called Smart. Due to the long signal delay and high error rate from Earth, the rover makes autonomous decisions based on several decision factors, such as weather, landform, energy status, and mined ore count. For each factor, there are exactly two possible conditions (for example, weather may be either sunny or windy).

Scientists predefine several decision conditions; each condition is a list of decisions corresponding to the N factors. To speed up the decision-making process, an intelligent induction module summarizes all these conditions into a single decision template. The template is a sequence of N fields where each field is either a fixed value or a wildcard symbol *, meaning that the corresponding factor does not affect the decision. The template must cover all the provided decision conditions, and at the same time, the number of wildcards should be minimized.

The rule to form the minimal decision template is simple: For each factor, if all decision conditions have the same value then that value is used in the template; otherwise, a wildcard * is used. For instance, consider the following decision conditions for a mining operation (with factors in order: Weather, Landform, Energy, Mine):

The minimal decision template is:

This template covers all the conditions and uses as few wildcards as possible.

Input Format: The first line contains two integers \(N\) and \(M\), where \(N\) is the number of decision factors and \(M\) is the number of decision conditions. Each of the following \(M\) lines contains \(N\) space-separated strings representing the conditions.

Output Format: Output a single line containing \(N\) tokens separated by a space. For the \(i\)-th token, if all \(M\) conditions have the same value at the \(i\)-th factor, output that value; otherwise, output a wildcard symbol *.

inputFormat

The first line contains two integers \(N\) (the number of decision factors) and \(M\) (the number of decision conditions).

Then \(M\) lines follow, each containing \(N\) space-separated strings. Each string represents the condition for the corresponding factor in that decision condition.

Example:

4 3
sunny Plain full Few
sunny mountain full Many
sunny mountain full Many

outputFormat

Print a single line with \(N\) tokens separated by a space. For each factor, if all \(M\) conditions are the same, print that value; otherwise, print *.

Example Output:

sunny * full *

sample

4 3
sunny Plain full Few
sunny mountain full Many
sunny mountain full Many

sunny * full *