Эта задача сделана как интерактивная. Это означает, что ваше решение будет считывать входные данные, которые вывел интерактор. Однако, интерактор выведет полные входные данные в начале, и после этого вы должны будете вывести ответ. Поэтому вы должны решать задачу так, как если бы вы решали обычную, не интерактивную задачу, потому что у вас не будет никакого процесса взаимодействия. Единственная вещь, про которую вы не должны забыть — это сбросить буфер выходного потока после вывода ответа. Иначе ваше решение может получить вердикт «Решение «зависло»». Обратитесь к руководству по интерактивным задачам для более детальной информации про сброс буфера выходного потока.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$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$$$, описывающая способ, которым строки будут перемешаны. Строки будут расположены в том порядке, в котором индексы следуют в перестановке, индекс украденной строки при этом будет пропущен.