Морской бой
Когда играют в морской бой, игроки по очереди пытаются потопить флот противника. Каждый игрок может делать выстрелы по одной координате за раз. Если игрок попадает в один из кораблей противника и у противника остаются другие корабли, он может продолжить. В противном случае, другой игрок начинает стрелять. После попадания в корабль по одной координате, повторный выстрел по этой координате считается промахом. Игра заканчивается, когда все части всех кораблей флота одного из игроков поражены. Первый игрок начинает, и каждый игрок получает одинаковое количество ходов. Это означает, что второй игрок может получить еще один ход, даже если все его корабли потоплены. Игра заканчивается вничью, если оба флота полностью потоплены, или если остаются корабли после того, как все выстрелы сделаны.
Маленький шпион Том наблюдает за игрой в морской бой между двумя адмиралами флота. Поскольку он успешно подключился к коммуникационным линиям, он может перехватывать приказы на выстрелы. Однако он не смог определить, какой адмирал отдал приказ на какой выстрел. После игры он успешно проникает в сверхсекретное управление игрой и получает карты развертывания флота. Поскольку он хочет определить, какой адмирал флота более опасен, он хочет узнать, какой адмирал победил. Он передает карты развертывания и приказы на выстрелы и хочет, чтобы вы определили, какой адмирал победил.
Входные данные
Ввод начинается с одной строки, содержащей количество тестов t (0 < t ≤ 20). Каждый тест начинается со строки, содержащей три целых числа w, h и n (1 ≤ w, h ≤ 30; 1 ≤ n ≤ 2000), описывающих ширину и высоту карт развертывания флота и количество выстрелов. Следующие h строк содержат карту развертывания для игрока один. Каждая строка содержит w описаний полей, где '_' означает "вода" и '#' означает "корабль". Затем следуют h строк, содержащих карту развертывания для игрока два.
Следующие n строк содержат приказы на выстрелы; каждый приказ состоит из двух целых чисел, координат x и y выстрела. Координата x указывает на столбец выстрела, от 0 до w-1, где 0 означает самый левый столбец. Координата y указывает на строку выстрела, от 0 до h-1, где 0 означает последнюю строку, а h-1 означает первую строку соответствующей карты.
Обратите внимание, что может быть больше приказов на выстрелы, чем необходимо для завершения игры.
Выходные данные
Для каждого теста выведите одну из строк "победил игрок один", "победил игрок два" или "ничья", в отдельной строке.