В игре Lizard Era: Beginning главному герою предстоит путешествие с тремя спутницами: Линн, Мелианой и Ворриган. Всего в игре n обязательных заданий, для выполнения каждого из них нужно взять ровно двух спутниц.
Отношение каждой из спутниц к герою характеризуется целым числом. Изначально отношение каждой из них к герою нейтрально и равно 0. В процессе выполнения задания главный герой совершает поступки, которые изменяют отношение к нему спутниц, которых он взял на выполнение этого задания, в положительную или отрицательную сторону (а могут и не менять вовсе).
Сообщите, каких спутниц нужно выбирать главному герою, чтобы после выполнения всех заданий значения их отношения к герою были равны между собой. Если это можно сделать несколькими способами, выберите тот, в котором эти значения наибольшие.
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа li, mi, wi — величины, на которые изменятся отношения к главному герою Линн, Мелианы или Ворриган соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. Все числа во входных данных целые и не превышают по абсолютному значению 107.
В случае, если решения не существует, в первой строке выведите "Impossible".
В противном случае выведите n строк, в каждой из них по два символа — в i-й строке выводите первые буквы имен спутниц, которых герой должен взять с собой на выполнение i-ого задания ('L' — Линн, 'M' — Мелиана, 'W' — Ворриган). Буквы выводите в любом порядке. Если решений несколько, выведите любое.
3
1 0 0
0 1 0
0 0 1
LM
MW
MW
7
0 8 9
5 9 -2
6 -8 -7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
LM
MW
LM
LW
MW
LM
LW
2
1 0 0
1 1 0
Impossible
| Codeforces Round 325 (Div. 1) |
|---|
| Закончено |
