У AquaMoon было \(n\) строк длины \(m\) каждая. \(n\) — нечетное число.
Когда AquaMoon отошла, Cirno попыталась разбить эти \(n\) строк на пары. После того, как она сделала \(\frac{n-1}{2}\) пару, она обнаружила, что осталась ровно одна строка без пары!
В гневе она перемешала каждую пару строк. Для каждой пары она выбрала некоторые позиции (хотя бы \(1\) и не более, чем \(m\)) и обменяла символы в двух строках этой пары на выбранных позициях.
Например, если \(m = 6\) и две строки «abcdef» и «xyzklm» в одной паре и Cirno выбрала позиции \(2\), \(3\) и \(6\) она поменяет 'b' с 'y', 'c' с 'z' и 'f' с 'm'. В результате строки станут «ayzdem» и «xbcklf».
Затем Cirno украла строку, оставшуюся без пары, и расположила все оставшиеся строки в некотором порядке.
AquaMoon обнаружила оставшуюся \(n-1\) строку в полном беспорядке. Также, она помнит изначальные \(n\) строк. Она хочет узнать, какую строку украли, но она не очень хороша в программировании. Можете ли вы помочь ей?
Входные данные
Эта задача сделана как интерактивная. Это означает, что ваше решение будет считывать входные данные, которые вывел интерактор. Однако, интерактор выведет полные входные данные в начале, и после этого вы должны будете вывести ответ. Поэтому вы должны решать задачу так, как если бы вы решали обычную, не интерактивную задачу, потому что у вас не будет никакого процесса взаимодействия. Единственная вещь, про которую вы не должны забыть — это сбросить буфер выходного потока после вывода ответа. Иначе ваше решение может получить вердикт «Решение «зависло»». Обратитесь к руководству по интерактивным задачам для более детальной информации про сброс буфера выходного потока.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число \(t\) (\(1 \leq t \leq 100\)) — количество наборов входных данных.
В первой строке описания каждого набора входных данных содержится два целых числа \(n\), \(m\) (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\)) — количество строк и длина каждой строки, соответственно.
Следующие \(n\) строк каждая содержат строку длины \(m\), описывающую изначальные \(n\) строк. Все строки состоят из символов латинского алфавита в нижнем регистре.
Следующая \(n-1\) строка каждая содержит строку длины \(m\), описывающую строки, после того, как Cirno сделала обмены и переставила их.
Гарантируется, что \(n\) нечетно и что сумма \(n \cdot m\) по всем наборам входных данных не превосходит \(10^5\).
Формат теста для взлома:
В первой строке должно находиться единственное целое число \(t\). После этого должно следовать описание \(t\) наборов входных данных в следующем формате:
В первой строке должно находиться два целых числа \(n\) и \(m\).
В следующих \(n\) строках должны быть записаны \(n\) строк длины \(m\), описывающих изначальные строки.
Следующие \(\frac{n-1}{2}\) строк должны описывать пары. Каждая должна содержать в следующем порядке: индекс первой строки \(i\) (\(1 \leq i \leq n\)), индекс второй строки \(j\) (\(1 \leq j \leq n\), \(i \neq j\)), количество позиций для обмена \(k\) (\(1 \leq k \leq m\)) и список из \(k\) позиций, в которых будет сделан обмен (\(k\) различных индексов от \(1\) до \(m\) в любом порядке).
В последней строке должна находиться перестановка из целых чисел от \(1\) до \(n\), описывающая способ, которым строки будут перемешаны. Строки будут расположены в том порядке, в котором индексы следуют в перестановке, индекс украденной строки при этом будет пропущен.
Выходные данные
Для каждого набора входных данных выведите украденную строку в единственной строке.
Примечание
В первом наборе входных данных в строках «aaaaa» и «bbbbb» обменяли все позиции и «ccccc» является украденной строкой.
Во втором наборе входных данных в строках «aaaa» и «bbbb» обменяли первые две позиции и «cccc» является украденной строкой.
Это первый тест, записанный в формате для взломов:
3
3 5
aaaaa
bbbbb
ccccc
1 2 5 1 2 3 4 5
2 1 3
3 4
aaaa
bbbb
cccc
1 2 2 1 2
2 1 3
5 6
abcdef
uuuuuu
kekeke
ekekek
xyzklm
1 5 3 2 3 6
2 4 3 2 4 6
5 4 1 2 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 5
aaaaa
bbbbb
ccccc
aaaaa
bbbbb
3 4
aaaa
bbbb
cccc
aabb
bbaa
5 6
abcdef
uuuuuu
kekeke
ekekek
xyzklm
xbcklf
eueueu
ayzdem
ukukuk
|
ccccc
cccc
kekeke
|