Students - free of charge!
The Great Galactic Theater's hall is organized into S rows, each containing S seats. Ticket sales for each performance proceed as follows: the first S^2-N art enthusiasts can purchase tickets for any available seats of their choice. The remaining N seats are then allocated free of charge to students by the administration, in keeping with a long-standing tradition.
To prevent accusations of gender discrimination, the allocation of these N student seats must adhere to the following rules:
In each row, the difference between the number of female and male students must not exceed 1.
In each "vertical of seats" (i.e., seats with the same number across different rows), the difference between the number of female and male students must also not exceed 1.
Therefore, after selling tickets to the art enthusiasts, the organizers need to assign the remaining N seats to female and male students while complying with these rules.
Each seat in the hall is identified by two numbers ranging from 1 to S: the row number and the seat number within that row. The student seat number i is located in the a_i-th row and has the number b_i in that row. Since art enthusiasts may occupy any seats, the numbers a_i and b_i can be any values from 1 to S. It is possible that some rows may not have any student seats.
To streamline this process, the organizers request your assistance in writing a program that automates the distribution of student seats between male and female students.
Input
The input begins with two integers S and N (1 ≤ S ≤ 100000, 1 ≤ N ≤ min{100000, S^2}). Following this, N pairs of natural numbers (a_i, b_i) are provided, each not exceeding S. It is guaranteed that all seats are distinct.
Output
If it is impossible to achieve the desired arrangement, output Impossible. Otherwise, output a single line containing N characters: 'M' for male and 'W' for female. The character at the i-th position corresponds to the gender assigned to the i-th seat in the order they were listed in the input.