Codeforces Round 325 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

meet-in-the-middle

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Lizard Era: Beginning

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn the game Lizard Era: Beginning the protagonist will travel with three companions: Lynn, Meliana and Worrigan. Overall the game has *n* mandatory quests. To perform each of them, you need to take exactly two companions.

The attitude of each of the companions to the hero is an integer. Initially, the attitude of each of them to the hero of neutral and equal to 0. As the hero completes quests, he makes actions that change the attitude of the companions, whom he took to perform this task, in positive or negative direction.

Tell us what companions the hero needs to choose to make their attitude equal after completing all the quests. If this can be done in several ways, choose the one in which the value of resulting attitude is greatest possible.

Input

The first line contains positive integer *n* (1 ≤ *n* ≤ 25) — the number of important tasks.

Next *n* lines contain the descriptions of the tasks — the *i*-th line contains three integers *l*_{i}, *m*_{i}, *w*_{i} — the values by which the attitude of Lynn, Meliana and Worrigan respectively will change towards the hero if the hero takes them on the *i*-th task. All the numbers in the input are integers and do not exceed 10^{7} in absolute value.

Output

If there is no solution, print in the first line "Impossible".

Otherwise, print *n* lines, two characters is each line — in the *i*-th line print the first letters of the companions' names that hero should take to complete the *i*-th task ('L' for Lynn, 'M' for Meliana, 'W' for Worrigan). Print the letters in any order, if there are multiple solutions, print any of them.

Examples

Input

3

1 0 0

0 1 0

0 0 1

Output

LM

MW

MW

Input

7

0 8 9

5 9 -2

6 -8 -7

9 4 5

-4 -9 9

-4 5 2

-6 8 -7

Output

LM

MW

LM

LW

MW

LM

LW

Input

2

1 0 0

1 1 0

Output

Impossible

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/04/2023 22:35:50 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|