D. Студентам — бесплатно

В зале $S$ рядов по $S$ мест. Из них $N$ мест отданы студентам. Расставьте на этих местах юношей и девушек так, чтобы в каждом ряду и в каждой вертикали количества различались не более чем на единицу.

В первой строке $S$ и $N$ ($1 \le S \le 10^5$, $1 \le N \le \min(10^5, S^2)$). В каждой из следующих $N$ строк — пара $(a_i, b_i)$: номер ряда и номер места ($1 \le a_i, b_i \le S$). Все места различны.

Выведите строку из $N$ символов M и W — пол студента на соответствующем месте в порядке ввода. Если рассадки не существует, выведите Impossible.