在游戏《蜥蜴时代:开始》中,主角将与三位同伴一起旅行:Lynn、Meliana 和 Worrigan。总的来说,游戏有 n 个强制任务。要执行每一项任务,您都需要带上两名同伴。
每个同伴对英雄的态度都是一个整数。最初,他们每个人对英雄的态度都是中立的,等于0。当英雄完成任务时,他做出的行动会改变他带去执行这项任务的同伴的态度,无论是积极还是消极。
告诉我们英雄在完成所有任务后需要选择哪些同伴才能使他们的态度平等。如果可以通过多种方式做到这一点,请选择一种能够最大程度地产生态度价值的方法。
输入
第一行包含正整数 n (1 ≤ n ≤ 25) — 重要任务的数量。
接下来的 n 行包含任务的描述 - 第 i 行包含三个整数 li、mi、wi - 如果英雄让 Lynn、Meliana 和 Worrigan 执行第 i 个任务,则这些值将分别改变对英雄的态度。输入的所有数字均为整数,且绝对值不超过 107。
输出
如果无解,则在第一行打印“Impossible”。
否则,打印n行,每行两个字符——在第i行中打印英雄完成第i个任务时应采取的同伴名字的第一个字母(“L”代表Lynn,“M”代表Meliana,“W”代表Worrigan)。以任意顺序打印字母,如果有多个解决方案,则打印其中任何一个。
示例
输入 #1
3 1 0 0 0 1 0 0 0 1
输出 #1
LM MW MW
输入 #2
7 0 8 9 5 9 -2 6 -8 -7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7
输出 #2
LM MW LM LW MW LM LW
输入 #3
2 1 0 0 1 1 0
输出 #3
Impossible