Problems
Студентам - бесплатно!
Студентам - бесплатно!
Зал Большого галактического театра состоит из \textbf{S} рядов, по \textbf{S} мест в каждом ряду. Продажа билетов на каждый спектакль происходит по следующему принципу: первые \textbf{S^2}-\textbf{N} ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \textbf{N} кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.
Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \textbf{N} местам необходимо таким образом, чтобы:
\begin{itemize}
\item в каждом ряду количество девушек-студенток и количество юношей-студентов различалось бы не более чем на \textbf{1};
\item на каждой "вертикали мест" (т.е. местах, имеющих один и тот же номер, но расположенных в разных рядах) количество девушек-студенток и количество юношей-студентов также различалось бы не более чем на \textbf{1}.
\end{itemize}
Таким образом, после продажи билетов ценителям прекрасного билетёры должны распределить оставшиеся \textbf{N} кресел на женские и мужские с соблюдением этих правил.
Каждое место в зале определяется двумя числами от \textbf{1} до \textbf{S} - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \textbf{i} расположено в \textbf{a_i}-м ряду и имеет в нём номер \textbf{b_i}. Поскольку ценители прекрасного могли занять совершенно любые места, числа \textbf{a_i} и \textbf{b_i} могут принимать любые значения от \textbf{1} до \textbf{S}. В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.
Ради упрощения работы билетёров администрация обращается к вам с заданием написать программу, которая автоматизирует процесс распределения студенческих мест на мужские и женские.
\InputFile
Сначала вводятся два целых числа \textbf{S} и \textbf{N} (\textbf{1} ≤ \textbf{S} ≤ \textbf{100000}, \textbf{1} ≤ \textbf{N} ≤ \textbf{min}\{\textbf{100000}, \textbf{S^2}\}). Далее расположены \textbf{N} пар натуральных чисел (\textbf{a_i}, \textbf{b_i}), не превосходящих \textbf{S}. Гарантируется, что все места различные.
\OutputFile
Если искомого способа не существует, выведите \textbf{Impossible}. Иначе выведите единственную строку из \textbf{N} символов '\textbf{M}' (мужское) и '\textbf{W}' (женское). Символ на \textbf{i}-й позиции соответствует статусу \textbf{i}-го места в той же нумерации, в которой они были перечислены во входных данных.
Input example #1
2 2 2 1 1 2
Output example #1
MW