הפרות משחקות דמקה בהתלהבות. למרות ההנאה האינסופית, הן גרועות בסיום המשחק ורוצות עזרה.

ללוח $N\times N$, $(4 \le N \le 30)$, מצאו רצף מיטבי המסיים את המשחק בתור הבא. הכלים נעים רק על + ולוכדים בדילוג מעל יריב, שמוסר מיד. דוגמה עם $N=8$:

- + - + - + - +
+ - + - + - + -
- + - K - + - +
+ - + - + - + -
- o - o - + - +
+ - K - + - + -
- o - + - + - +
+ - K - + - K -

K הם המלכים של Bessie ו-o כלי היריב. Bessie תמיד משחקת בתור הבא. המלכים מדלגים ברצף מעל היריבים בכל כיוון אלכסוני ומסירים את הנלכדים. כאן המלך השמאלי התחתון מדלג על כל שלושת היריבים ומסיים. K הנע מסומן >K<.

- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

משמאל לימין: מקורי, אחרי מהלך 1, אחרי מהלך 2, אחרי מהלך 3.

המהלכים עוברים במשבצות הבאות:

  1 2 3 4 5 6 7 8
1 - + - + - + - +
2 + - + - + - + -
3 - + - K - + - +
4 + - * - + - + -
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -

שורה, עמודה; התחלה: $(8,3)$; מהלכים: $(6,1)$, $(4,3)$, $(6,5)$.

מצאו רצף מסיים משחק ללוח הקלט $N\times N$, אם קיים (הוא למעשה יחיד). יש לפחות מלך אחד וכלי יריב אחד.

קלט

• שורה 1: שלם $N$.

• שורות $2,\ldots,N+1$: שורה $i+1$ מכילה $N$ תווי -, +, K או o, המתארים שורה $i$ בלוח תקין.

פלט

• משורה 1: אם אי אפשר, הדפיסו impossible לבד בשורה. אחרת בכל שורה שני שלמים מופרדים ברווח, מיקומים עוקבים של מלך שמהלכיו מנצחים.

דוגמאות

קלט 1

8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

פלט 1

8 3
6 1
4 3
6 5

מחבר הבעיה: Rob Kolstad, 2008