Democratic Naming

Interview

Time limit1sMemory limit1024 MB

Summary

Given n city names of length m, build the county name by picking, for each position, the letter most cities have there, breaking ties alphabetically.

Level: Easy2 of 10
Topics: Array, Hash map, Implementation
Solved: No attempts yet

Problem

The county was created on artificially made land off the coast, with the code name "Built Anew Peninsula County", but its final name still needs to be chosen. The cities in the county vote on the individual letters of the name.

All cities in the county have a name with exactly $m$ letters, so the county name also has exactly $m$ letters. Each city prefers its own name, so it votes that the $i$ th letter of the county name matches its own $i$ th letter. For each of the $m$ positions, the letter with the most votes is picked. If several letters tie, the one earliest in the English alphabet is picked.

Given the city names, determine the result of the vote for the county name.

Input

The first line has two integers $n$ and $m$ ( $1\leq n\leq 1000$ , $1 \leq m \leq 1000$ ), the number of cities and the number of letters in each city name.

Each of the next $n$ lines has a string of length $m$ , the name of a city. The names consist only of lowercase English letters (a-z).

Output

Output the name of the new county.

Examples2

Example 1
Input
```
3 5
apple
maple
alpha
```
Expected output
```
aaple
```
Example 2
Input
```
3 4
icpc
back
laps
```
Expected output
```
bapc
```