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

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Linear Algebra
• Math > Number Theory
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > Graphs