Морський бій#3773
У грі "Морський бій" гравці по черзі намагаються потопити флот суперника. Кожен гравець може стріляти по одній координаті за раз. Якщо постріл влучає в корабель противника і у нього залишаються інші кораблі, гравець продовжує стріляти. В іншому випадку, право стріляти переходить до іншого гравця. Після влучання в корабель на певній координаті, повторний постріл по цій координаті вважається промахом. Гра завершується, коли всі частини кораблів одного з флотів знищені. Перший гравець починає, і кожен гравець має однакову кількість ходів. Це означає, що другий гравець може отримати ще один хід, навіть якщо всі його кораблі вже потоплені. Гра завершується внічию, якщо обидва флоти повністю знищені, або якщо залишаються кораблі після того, як усі постріли були зроблені.
Том, маленький шпигун, спостерігає за грою в "Морський бій" між двома адміралами. Завдяки підключенню до комунікаційних ліній, він може перехоплювати накази про постріли, але не знає, який адмірал віддав який наказ. Після гри він зламав суперсекретний центр управління і отримав карти розміщення флоту. Том хоче визначити, який адмірал є більш небезпечним, тому йому потрібно знати, хто виграв. Він передає карти розміщення і накази про постріли, і просить вас визначити переможця.
Вхід починається з одного рядка, що містить кількість тестових випадків (0 < t \le 20). Кожен тестовий випадок починається з рядка, що містить три цілі числа , і (1 \le w, h \le 30; 1 \le n \le 2000), які описують ширину і висоту карт розміщення флоту, а також кількість пострілів. Наступні рядків містять карту розміщення для першого гравця. Кожен рядок містить символів, де '_' означає "вода" і '#' означає "корабель". Потім слідують рядків, що містять карту розміщення для другого гравця.
Наступні рядків містять накази про постріли; кожен наказ складається з двох цілих чисел, координат і пострілу. Координата вказує на стовпець пострілу, що йде від до w-1, де означає лівий крайній стовпець. Координата вказує на рядок пострілу, що йде від до h-1, де означає останній рядок, а h-1 означає перший рядок відповідної карти.
Зверніть увагу, що може бути більше наказів про постріли, ніж потрібно для завершення гри.
Для кожного тестового випадку надрукуйте один з рядків "player one wins", "player two wins" або "draw".
Приклад 1