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