1. Сновида-2

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: sleep2.in
Вихідний файл: sleep2.out
Програма: sleep2.*

Грабіжникам стало відомо про звичку президента Першого національного Банку майора Томаса Б. Кiнгмена кожну ніч перекладати вміст сейфів, у яких клієнти банку зберігають свої коштовності. Шляхом погроз і підкупу співробітників банку злочинці з'ясували як змінилось розташування коштовностей після двох ночей. На жаль для грабіжників, ця інформація не дозволяє однозначно встановити алгоритм, за яким майор перекладає вміст сейфів.

Завдання
Створіть програму sleep2.* , яка обчислює кількість можливих алгоритмів перекладання, що за дві ночі приводять до відомого злочинцям результату, якщо алгоритм перекладання щоночі однаковий.

Вхідні дані
В першому рядку файлу sleep2.in записано єдине натуральне число N — кількість сейфів у банку (N ≤ 100). У другому рядку через прогалину записано N натуральних чисел a₁, a₂, …, a_N, що описують вміст сейфів після другої ночі. Кожне таке число належить діапазону [1..N] і зустрічається в рядку лише один раз. Тут a_i — номер сейфа в який коштовності потрапили з i-го сейфа за дві ночі перекладань.

Вихідні дані Єдиний рядок вихідного файлу sleep2.out має містити одне ціле число — результат обчислень.

Приклади

2. Карти

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: cards.in
Вихідний файл: cards.out
Програма: cards.*

Колода складається з парної кількості карт. Карти занумеровано послідовними натуральними числами від 1 до 2N (для певного натурального N) включно. З колодою роблять таке:

1. Спочатку колоду ділять на дві рівні частини. У першу частину потрапляють карти, що стояли на непарних місцях, в другу — ті карти, що були на парних місцях:
   (1, 2, …, 2N) → (1, 3, 5, …, 2N – 1) + (2, 4, …, 2N).

2. З обох утворених частин викидають карту, що розташована у відповідній частині на місці 1 + [aN/b] при 0 ≤ a < b ≤ 1000. Наприклад, якщо a = 0, b = 1, то буде викинуто першу карту:
   (1, 3, 5, …, 2N – 1) → (3, 5, 7, …, 2N – 1);
   (2, 4, 6, …, 2N) → (4, 6, 8, …, 2N).

3. Другу частину кладуть поверх першої:
   (3, 5, 7, …, 2N – 1) + (4, 6, 8, …, 2N) → (3, 5, 7, …, 2N – 1, 4, 6, 8, …, 2N).

Дії 1–3 повторюють доти, поки в колоді не залишиться лише 2 карти. Наприклад, якщо a = 1, b = 2, а початкова кількість карт — 2 · 5, маємо:

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) → (1, 3, 5, 7, 9) + (2, 4, 6, 8, 10) → (1, 3, 7, 9) + (2, 4, 8, 10)  → (1, 3, 7, 9, 2, 4, 8, 10) → (1, 7, 2, 8) + (3, 9, 4, 10) → (1, 7, 8) + (3, 9, 10) → (1, 7, 8, 3, 9, 10) → (1, 8, 9) + (7, 3, 10) → (1, 9) + (7, 10) → (1, 9, 7, 10) → (1, 7) + (9, 10) → (1) + (9) → (1, 9),

бо 1 + [5·1/2] = 3, 1 + [4·1/2] = 3, 1 + [3·1/2 ] = 2, 1 + [2·1/2] = 2.

Завдання
Визначте кінцевий стан колоди.

Вхідні дані
Вхідний файл містить 3 невід'ємні цілі числа N, a, b. 2 ≤ N ≤ 500 000.

Вихідні дані
Вихідний файл має містити два натуральних числа: номери карт, що залишаться. Номер нижньої карти потрібно вказати першим.

Приклад

3. Гра

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: game.in
Вихідний файл: game.out
Програма: game.*

Полем гри є декартова площина із двома групами занумерованих точок. Точки першої групи мають координати (0; і), де і — номер точки в групі (нумерація починається з 0). Точки другої групи мають координати (1; j), де j — номер точки в групі (нумерація також починається з 0).

Кожну точку пофарбовано у білий або у чорний колір.

Гравці ходять по черзі. За один хід гравець сполучає відрізком деяку точку А з першої групи з деякою точкою В з другої групи. При цьому справджуються такі умови:

• точки А і В — одного кольору;
• відрізок АВ не має спільних точок з довільним уже проведеним відрізком.

Гравець, що не може зробити наступний хід, програє.

Завдання

Для заданого ігрового поля вкажіть, чи може перший гравець забезпечити собі перемогу. Якщо відповідь ствердна, вкажіть усі переможні для нього перші ходи за умови оптимальності гри його суперника.

Вхідні дані
Перший рядок містить число M (0 ≤ M ≤ 20) — кількість точок у першій групі.
Другий рядок містить число N (0 ≤ N ≤ 20) — кількість точок у другій групі.
Третій рядок містить M чисел, що задають розфарбування точок першої групи (0 — чорний колір, 1 — білий колір).
Четвертий рядок містить N чисел, що задають розфарбування точок другої групи таким самим чином.

Вихідні дані
Якщо виграє другий гравець, єдиний рядок вихідного файлу містить слово LOSE.
Якщо виграє перший гравець, перший рядок вихідного файлу містить слово WIN, а наступні рядки перераховують виграшні перші ходи. Кожний рядок містить один з можливих ходів у такому форматі:

I J

Тут I — номер точки з першої групи, J — номер точки з другої групи. Кожен виграшний хід повинен зустрічатися один та лише один раз. Пари (I; J) потрібно подати в лексико­графічному порядку.

Приклади