Гра в плитки
Гра "Кахлі" — це змагання для двох учасників, яке відбувається на прямокутній дошці, що складається з R рядків і C стовпців квадратних клітинок, званих кахлями. На початку гри деякі кахлі можуть бути зафарбовані чорним кольором, тоді як інші залишаються білими. Гравці по черзі роблять ходи, і той, хто не зможе зробити допустимий хід, програє. Гравець 1 починає гру, вибираючи білу кахлю та пишучи на ній число 1. Кожен наступний хід i полягає у написанні числа i на невикористаній білій кахлі, яка прилягає горизонтально або вертикально (але не по діагоналі) до кахлі з числом i-1. Зверніть увагу, що Гравець 1 завжди пише непарні числа, а Гравець 2 — парні.
На наступній ілюстрації показано три приклади можливих конфігурацій дошки з R = 3 і C = 4 під час гри. Ліворуч зображено початкову конфігурацію. У центрі показано проміжний стан, де сірим кольором позначено можливі ходи для Гравця 2. Праворуч зображено конфігурацію, коли Гравець 2 виграє, зробивши відповідний хід.
Ваше завдання — створити програму, яка визначить, який гравець виграє, якщо обидва гратимуть оптимально, виходячи з початкової конфігурації дошки.
Вхідні дані
Кожен тестовий випадок описується кількома рядками. Перший рядок містить два цілі числа R і C, що вказують на кількість рядків і стовпців дошки (1 ≤ R, C ≤ 50). i-й з наступних R рядків містить рядок B_i з C символів, що описує i-й рядок початкової дошки. j-й символ B_i — це або '.' (крапка), або велика літера 'X', що означає, що кахля в рядку i і стовпці j відповідно біла або чорна. У кожному тестовому випадку принаймні одна з кахлів є білою.
Вихідні дані
Для кожного тестового випадку виведіть рядок з цілим числом, що представляє номер гравця (1 або 2), який виграє гру, якщо обидва гратимуть оптимально.