很容易想到可以对于每个任务选不去的那一个人进行搜索，时间复杂度 \(O(3^n)\)，明显过不了。
发现 \(n\le 25,\lceil \frac{n}{2}\rceil\le 13\)，且各个任务间不会互相影响，便可以用折半搜索分成 \(2\) 部分来搜最后来合并。
考虑如何合并两部分，令前一部分得到的值分别为 \(a, b, c\)，后一部分得到的值分别为 \(a', b', c'\)，若合法则有 \(a + a' = b + b' = c + c'\)。
做差得到新的等式 \(a - b = b' - a', a - c = c' - a'\)，则可以后半部分以 \((b' - a', c' - a')\) 来查找前半部分中的 \((a - b, a - c)\)，记录一下 \(2\) 个部分的 \(a,a'\)，求和即可。
对于方案输出，搜索时记录一下不选的数得出剩下选的数即可。
时间复杂度 \(O(3^{\lfloor \frac{n}{2}\rfloor}\log_2 3^{\lceil \frac{n}{2}\rceil})\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: D. Lizard Era: Beginning
// Contest: Codeforces - Codeforces Round 325 (Div. 1)
// URL: https://codeforces.com/problemset/problem/585/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, mid;
int val[N][3];
map<pair<int, int>, pair<int, int> > mp;
int ans[N];
void dfs1(int w, int a, int b, int c, int s) {
if (w > mid) {
if (! mp.count({a - b, a - c})) {
mp[{a - b, a - c}] = {a, s};
}
else if (a > mp[{a - b, a - c}].first) {
mp[{a - b, a - c}] = {a, s};
}
return ;
}
dfs1(w + 1, a + val[w][0], b + val[w][1], c, s * 3 + 2);
dfs1(w + 1, a + val[w][0], b, c + val[w][2], s * 3 + 1);
dfs1(w + 1, a, b + val[w][1], c + val[w][2], s * 3 + 0);
return ;
}
int p1, p2, pmax = INT_MIN;
void dfs2(int w, int a, int b, int c, int s) {
if (w > n) {
if (mp.count({b - a, c - a})) {
if (mp[{b - a, c - a}].first + a > pmax) {
pmax = mp[{b - a, c - a}].first + a, p1 = mp[{b - a, c - a}].second, p2 = s;
}
}
return ;
}
dfs2(w + 1, a + val[w][0], b + val[w][1], c, s * 3 + 2);
dfs2(w + 1, a + val[w][0], b, c + val[w][2], s * 3 + 1);
dfs2(w + 1, a, b + val[w][1], c + val[w][2], s * 3 + 0);
return ;
}
int main() {
scanf("%d", &n);
mid = (1 + n) >> 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
scanf("%d", &val[i][j]);
}
}
dfs1(1, 0, 0, 0, 0);
dfs2(mid + 1, 0, 0, 0, 0);
if (pmax != INT_MIN) {
for (int i = mid; i; i--) {
ans[i] = p1 % 3, p1 /= 3;
}
for (int i = n; i > mid; i--) {
ans[i] = p2 % 3, p2 /= 3;
}
for (int i = 1; i <= n; i++) {
if (ans[i] != 0) {
printf("L");
}
if (ans[i] != 1) {
printf("M");
}
if (ans[i] != 2) {
printf("W");
}
printf("\n");
}
}
else {
printf("Impossible");
}
return 0;
}