Гризь#6392

Гризь

1 секунда

64 мегабайти

Складна

Гризь — це стратегічна гра для двох гравців, яку грають на прямокутній плитці шоколаду, що складається з маленьких квадратних плиток (клітинок). Гравці по черзі обирають одну плитку й «з’їдають» її (видаляють з поля разом із усіма плитками, що розташовані вище й правіше за неї). Ліва нижня клітинка є отруєною, і гравець, який змушений її з’їсти, програє. На діаграмі нижче показано гру, яка починається зі 3 на 3 плитки. Х — це отруєна клітинка.

Позиція є виграшною, якщо існує хід, після якого суперник потрапляє у програшну позицію. Позиція є програшною, якщо кожен хід із неї або веде до з’їдання отруєної плитки (і поразки), або залишає суперника у виграшній позиції.

У наведеному вище прикладі позиції 1×1 і L-подібні з рівними сторонами є програшними (оскільки суперник може дзеркально відповідати на ходи поточного гравця).

Позиції 3×3, L-подібні з різними сторонами та 1×n є виграшними.

Мета цієї задачі — «розв’язати» гру 3 на 100 Гризь. Тобто, для кожної можливої позиції визначити, виграшна вона чи програшна, а якщо виграшна — вказати наступний хід.

Позиція у грі 3 на 100 Гризь визначається кількістю $p$ клітинок у нижньому ряду, $q$ — у середньому ряду й $r$ — у верхньому ряду, де

100 \geq p \geq q \geq r \geq 0

100 \geq p \geq q \geq r \geq 0

Напишіть програму, яка для кожної можливої позиції у грі 3 на 100 Гризь визначає, чи є вона виграшною чи програшною, і якщо позиція виграшна — вказує наступний хід (клітинку, яку потрібно з’їсти).

Вхідні дані

Перший рядок містить єдине число $P$ ( $1 \leq P \leq 1000$ 1 \leq P \leq 1000), яке означає кількість наборів даних. Кожен набір потрібно обробити незалежно.

Кожен набір даних задається одним рядком. У ньому наведено номер набору $K$ , а потім через пробіл кількість клітинок $p$ , $q$ , $r$ ( $100 \geq p \geq q \geq r \geq 0$ 100 \geq p \geq q \geq r \geq 0) у нижньому, середньому та верхньому рядах відповідно.

Вихідні дані

Для кожного набору даних виведіть один рядок. Якщо позиція програшна, виведіть номер набору $K$ , пропуск і велику літеру L. Інакше (якщо позиція виграшна) — номер набору $K$ , велику літеру W, а також через пробіл номер колонки та номер рядка клітинки, яку потрібно з’їсти, щоб перевести суперника у програшну позицію.

Приклади

Приклад 1