All Tracks Algorithms String Algorithms String Searching Problem

Hamming
Tag(s):

Algorithms, Easy

Problem
Editorial
Analytics

It is Raful's birthday, and his friends gave him $$N$$ strings of length $$M$$. But he is not happy, because he wants only one beautiful string $$S$$.

His friends are upset now. You, as the best programmer in Lalalandia, decided to help them.

The string $$S$$ is considered beautiful only when the sum of the Hamming distances between it and each of the $$N$$ strings is minimal. If there exist several such strings, print out the lexicographically smallest one.

Input format

The first line of the input contains two integers $$N$$, $$M$$ - number of strings and their lengths respectively.

Then $$N$$ lines follow, each containing a string $$s_i$$ ($$1 \le i \le N$$), each consists of lowercase English letters.

Output format

The only line of the output should contain the string $$S$$.

Constraints:

$$1 \le N * M \le 100000$$

Note

You can learn more about Hamming distance here:

https://en.wikipedia.org/wiki/Hamming_distance

SAMPLE INPUT
4 1
a
b
c
d
SAMPLE OUTPUT
a
Explanation

In this sample, "a" is lexicographically minimal string among all valid answers.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications