Задача I. Игра в слова

Автор:Завгороднев А.А., Бадерик М.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

Миша и Паша играют в игру со словами. Игра достаточно трудная и правила у нее замудренные. Миша называет слово длины n, а Паша должен выбрать из раннее сказанных слов наиболее непохожее на только что сказанное.

Слова состоят из строчных латинских букв.

“Непохожесть“ слова а на слово b определяется по следующей формуле:

oversetni = 1((ai − bi)⋅ 100i − 1, если ai ≥ bi)

oversetni = 1((bi − ai + 50)⋅ 100i − 1, если ai < bi)

Где i - индекс буквы, ai, bi - алфавитные номера букв в словах на i-ом месте.

В нашем случае a - одно из раннее сказанных слов, b - только что сказанное слово.

В первый раунд Паше отвечать не нужно.

Пояснение

Непохожесть слова code на слово work вычисляется следующим образом:

порядок букв в алфавите:

с − 3, o − 15, d − 4, e − 5

w − 23, o − 15, r − 18, k − 11

(23 − 3 + 50)1000 + (15 − 15)1001 + (18 − 4 + 50)1002 + (11 − 5 + 50)1003 = 56640070

Формат входных данных

В первой строке располагается два целых числа n и k - длина слова и количество ходов в игре.

В следующих k строках располагаются строки длины n - слова, которые говорит Миша.

Формат выходных данных

Вам необходимо вывести k − 1 слов - ответы Паши.

Ограничения

1 ≤ n ≤ 6000 1 ≤ k ≤ 300

Примеры тестов

Стандартный вход Стандартный выход
1
3 5
abd
cdc
zdd
ccd
zxc
abd
cdc
cdc
abd
2
4 4
code
work
tthe
best
code
work
code

0.092s 0.015s 13