Codeforces Round 644 (Div. 3) |
---|
Закончено |
Вам даны $$$n$$$ строк $$$a_1, a_2, \ldots, a_n$$$, все они имеют одинаковую длину $$$m$$$. Строки состоят из строчных букв латинского алфавита.
Найдите любую такую строку $$$s$$$ длины $$$m$$$, что каждая из заданных $$$n$$$ строк отличается от $$$s$$$ не более чем в одной позиции. Формально, для каждой заданной строки $$$a_i$$$ должно существовать не более одной позиции $$$j$$$, в которой $$$a_i[j] \ne s[j]$$$.
Заметим, что искомая строка $$$s$$$ может как совпадать с одной из заданных строк $$$a_i$$$, так и отличаться от всех заданных строк.
Например, если вам даны строки abac и zbab, тогда ответом на задачу может быть строка abab, которая отличается от первой только последним символом, а от второй только первым.
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов тестовых данных в тесте. Далее записаны $$$t$$$ наборов тестовых данных.
Каждый набор начинается со строки, в которой записаны целые числа $$$n$$$ ($$$1 \le n \le 10$$$) и $$$m$$$ ($$$1 \le m \le 10$$$) — количество заданных строк и их длина.
Далее следуют $$$n$$$ строк $$$a_i$$$. Каждая имеет длину $$$m$$$ и состоит из строчных латинских букв.
Выведите $$$t$$$ ответов на наборы тестовых данных. Каждый ответ (если он существует) — это строка длины $$$m$$$, состоящая из строчных латинских букв. Если существует несколько ответов, то выведите любой из них. Если ответа не существует, выведите «-1» («минус один», без кавычек).
5 2 4 abac zbab 2 4 aaaa bbbb 3 3 baa aaa aab 2 2 ab bb 3 1 a b c
abab -1 aaa ab z
Первый набор тестовых данных примера разобран в условии.
Во втором наборе ответа не существует.
Название |
---|