Зал Великого галактичного театру складається з \(𝑆\)  рядів, по \(𝑆\)  місць в кожному ряду. Продаж квитків на кожний спектакль відбувається за наступним принципом: перші \(𝑆^2−𝑁\) поціновувачів прекрасного купують квитки на будь-які місця за їх смаком, а решту \(N\) місць адміністрація безплатно  виділяє студентам, віддаючи данину традиціям, що склалися.

Щоб уникнути звинувачень у дискримінації за статевою ознакою, розсаджувати студентів за цими місцями необхідно таким чином, щоб:

• у кожному ряді кількість дівчат-студенток і кількість юнаків-студентів відрізнялася б не більше ніж на 1;
• на кожній "вертикалі" місць (тобто місць, що мають один і той же номер, але розташованих у різних рядах) кількість дівчат-студенток і кількість юнаків-студентів також відрізнялася би не більше ніж на 1.

Таким чином, після продажу квитків поціновувачам прекрасного касири повинні розподілити \(N\) крісел, що залишилися, на жіночі і чоловічі з дотриманням цих правил.

Кожне місце в залі визначається двома числами від 1 до \(S\) - номером ряду і номером самого місця в цьому ряду. Студентське крісло номер \(𝑖\) розташоване в \(𝑎_𝑖\) -му ряду і має в ньому номер \(𝑏_𝑖\) . Оскільки цінителі прекрасного могли зайняти абсолютно будь-які місця, числа \(𝑎_𝑖\) і \(𝑏_𝑖\) можуть набувати будь-яких значень від 1 до \(𝑆\). Зокрема, може виявитися так, що в якомусь ряду не буде жодного студентського місця.

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

Формат вхідних даних

Спочатку вводяться два цілих числа \(𝑆\) і \(𝑁\) (\(1≤𝑆≤100000\) , \(1≤𝑁≤min(100000,𝑆^2) \)).

Далі розташовані \(N\) пар натуральних чисел (\(a_i,b_i\)), що не перевершують \(S\). Гарантується, що всі місця є різними.

Формат вихідних даних

Якщо шуканого способу не існує, виведіть Impossible. Інакше виведіть єдиний рядок з символів 'M' (чоловіче) і 'W' (жіноче). Символ на \(𝑖\) -й позиції відповідає статусу \(𝑖\) -го місця в тій же нумерації, в якій вони були перераховані у вхідних даних.

Оцінювання

Тести складаються із чотирьох груп.

• Тести 1 і 2. Тести за умови, оцінюються в 0 балів.
• Тести 3-19. В них \(𝑆≤1000\), \(𝑁≤30\). Група оцінюється в 30 балів, бали нараховуються тільки при проходженні всіх тестів групи.
• Тести 20-30. В них \(𝑆≤1000\), \(𝑁≤1000\). Група оцінюється в 30 балів, бали нараховуються тільки при проходженні всіх тестів групи.
• Тести 31-34. повні обмеження.

Приклад вхідних даних

2 2
2 1
1 2

Приклад вихідних даних

MW

Приклад вхідних даних

3 5
1 2
2 3
1 3
2 1
1 1

Приклад вихідних даних

WMWWM