Королева та король зустрілись на шаховій дошці 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 - сумарна кількість ходів, необхідних для виграшу відповідній стороні.