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