Королева и король встретились на шахматной доске N×N, на которой вырезаны некоторые клетки. Каждый из них хочет съесть другого. Выведите количество ходов, необходимое для этого, при оптимальной игре сторон (выигрышной позицией считается та, в которой проигрывающей стороне некуда деться, кроме как встать под бой - см. примеры).
Ходить на вырезанные клетки или перепрыгивать через них фигурам запрещается. Бить через вырезанные клетки, естественно, тоже нельзя.
Если какая-то из фигур заперта, то она считается находящейся в безопасности, и игра закончится вничью.
Известно, что ферзь и король находятся на разных клетках, и на текущем ходу фигура, которая ходит, не может съесть другую.
В первой строке входного файла даны два числа N и M (2 ≤ N ≤ 12, 0 ≤ M ≤ 142), где M - число вырезанных клеток. Следующие M строк содержат координаты вырезанных клеток, а в последней строке даны координаты королевы и координаты короля, а также информация о том, чей сейчас ход ('Q', если королевы, 'K', если короля).
Выведите одно из трёх сообщений:
"Queen wins in i moves", "King wins in i moves.", "The game will end in a draw". Здесь i - суммарное число ходов, необходимых для выигрыша соответствующей стороне.