In the game Lizard Era: Beginning the protagonist will travel with three companions:…
- User
In 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 li, mi, wi — 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 107 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
Assistant
We need to solve the problem: Given n (<=25) tasks. Each task i has three integers (li, mi, wi). For each task we must choose exactly two companions (so a pair among {L, M, W}). The effect: for each chosen companion, their attitude changes by the given value for that companion? Actually the description: "the i-th line contains three integers li, mi, wi — 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." So if we take for a task exactly two companions, then each of those two companions' attitudes are increased by the corresponding numbers. The third companion not taken stays unchanged.
We need after all n tasks that the three companions' attitudes (final total sums) are all equal. And we want to maximize that common value (if multiple solutions). Output the sequence of pairs.
We need to decide for each task which pair to take.
Constraints: n <= 25. That suggests we can use meet-in-the-middle. Because 2^25 is too big, but we can split into two halves of about 12-13 tasks each, and then combine.
Define for each task we have three possible choices (3 pairs). Actually number of pairs: choose 2 out of 3 = 3 pairs: LM, LW, MW. So each task has 3 options. So total possibilities: 3^n, which is huge.
We need to find a selection of options such that final sums for L, M, W are equal.
Let A_i = (l_i, m_i, w_i) denote the changes for each companion if taken.
If we choose pair p (e.g., LM), then the net change to the sum for L is l_i, for M is m_i, for W is 0? Wait: If we take LM, then Lynn and Meliana get the values l_i and m_i, but Worrigan gets 0. Similarly, for LW, Lynn gets l_i, Worrigan gets w_i, Meliana 0. For MW, Meliana gets m_i, Worrigan gets w_i, Lynn 0.
Thus each selection contributes a vector Δ = (ΔL, ΔM, ΔW). For each task i, we have three possible Δ vectors:
- Option LM: (l_i, m_i, 0)
- Option LW: (l_i, 0, w_i)
- Option MW: (0, m_i, w_i)
We need total sum over i of Δ_i = (S_L, S_M, S_W) such that S_L = S_M = S_W = T (some value). We want maximize T.
Equivalently, we need S_L - S_M = 0, S_L - S_W = 0 (or similar). So two independent constraints. But we could also treat as we want vector (S_L - S_M, S_L - S_W) = (0,0). So we can define for each Δ, we compute (d1 = ΔL - ΔM, d2 = ΔL - ΔW). Then we need sum d1 = 0, sum d2 = 0. Alternatively we could use three variables but then we need equality, which gives two constraints.
Also the total T = S_L. Since we want maximize T, but note that if we shift all three equally, that doesn't affect constraints. However the objective is to maximize the common value. Since initial attitudes are 0, T is simply S_L = S_M = S_W.
So we need to find selection that makes sums equal and maximize S_L (or any). Since S_L = total sum of ΔL contributions. But note that if we have two constraints, we can incorporate objective into meet-in-the-middle by storing partial sums and then combining.
Approach: Split tasks into two halves: first half size n1 (say ceil(n/2) or floor), second half n2 = n - n1. For each half, enumerate all possible choices of options (3^{n1} possibilities). For each combination, compute cumulative sums:
Let sumL, sumM, sumW.
Alternatively compute the differences: d1 = sumL - sumM, d2 = sumL - sumW, and also total sumL (or total T). But note that when combining two halves, we need overall sums to be equal. That means:
sumL1 + sumL2 = sumM1 + sumM2 = sumW1 + sumW2.
Let T = that common value. Then we have:
sumL1 + sumL2 = sumM1 + sumM2 => (sumL1 - sumM1) + (sumL2 - sumM2) = 0 => d1_1 + d1_2 = 0. Similarly sumL1 + sumL2 = sumW1 + sumW2 => d2_1 + d2_2 = 0.
So the condition is that the differences sum to zero.
Also we have T = sumL1 + sumL2. We want to maximize T.
Thus we can for first half enumerations, record for each combination (d1, d2) we also have sumL (or maybe sumL and also other sums to compute T?). But given that we need to maximize T, we can, for each (d1,d2) pair from first half, store the maximum sumL (or maximum T?) achievable for that (d1,d2). However when combining with second half, we need to match (-d1, -d2) from second half, and then T_total = sumL1 + sumL2. So if we have for each (d1,d2) in first half the maximum sumL1, and similarly for second half we have for each (d1,d2) the maximum sumL2 (or we can store all possibilities and then choose combination that gives maximum total). But we can do meet-in-the-middle: enumerate second half and for each second half combination compute its (d1, d2) and sumL2, and then lookup in a map for first half with key (-d1, -d2) to see if there is any. Among all such matches, we want to maximize sumL1+sumL2. Also need to reconstruct choices.
So plan:
-
n <= 25. Let n1 = n//2 (floor), n2 = n - n1. For typical meet-in-the-middle, we can take n1 = 12, n2 = 13 if n=25.
-
For each half, generate all 3^{n_i} possibilities. For each, we will store:
- The (d1, d2) as a pair of integers (could be large: sum of up to 13 * 10^7 = 1.3e8, within 32-bit signed? Actually values up to 1e7 absolute, times up to 12: 12e7 = 120 million, times maybe 2 for differences? But sumL could be up to 25*1e7=2.5e8, which fits in 32-bit signed? 2.5e8 < 2^31, so int is fine). Use Python int anyway.
- Also sumL (or maybe T from that half? Actually final T = sumL_total, but sumL from each half directly adds.
- Also need to store the sequence of choices for that half to reconstruct later. For each half we can store for each combination a "mask" that encodes the chosen options per task. Since we have at most 3 options, we can encode each choice in 2 bits (since 3 values need 2 bits) for each task. For n1 up to 13, the mask can be represented as an integer (say 2 bits per task). Or we can store the actual string of options (e.g., 'LM','LW','MW') but that would be memory heavy. Better to encode as an integer and later decode.
-
For the first half, we need a map from (d1, d2) to (max_sumL1, mask1) that yields that max sumL for that key. Because for each (d1,d2) there could be many combinations; we only need one that gives max sumL for that pair to maximize total. However careful: Could it be that using a combination with a lower sumL1 but higher sumL2 might give larger total? Actually if we fix key (-d1,-d2) from second half, we want the best sumL1 among those with (d1,d2) key. Since sumL_total = sumL1 + sumL2, for each second half combination with (d2_d1, d2_d2) and sumL2, we look up first half with key (-d2_d1, -d2_d2). Among all first half entries with that key, we would like the one with maximum sumL1. So it's sufficient to store for each (d1,d2) the maximum sumL1. That yields the best total when paired with any given sumL2. But we also need to later reconstruct. So we store (max_sumL1, mask1) for that key. If multiple with same sumL1, any is fine.
But is it possible that a first half combination with a slightly lower sumL1 leads to a better total because sumL2 might be higher when matching a different second half combination? However the lookup is per second half combination: For that particular second half combination (with its own sumL2), the best total with that specific key is achieved by picking the first half combination with that key that has maximum sumL1. So storing the maximum sumL1 is optimal for each key. Because sumL2 is fixed for that second half combination, the total is sumL1 + sumL2; maximizing sumL1 for that key maximizes total for that particular second half match. Then overall we consider all second half combinations, compute total for each match, and track the maximum total. So this works.
Alternative: We could store all combinations for first half and for second half, then sort and combine, but that would be more expensive. With n1=12, 3^12=531441, which is manageable; we can store all first half combos in a dictionary mapping (d1,d2) to best sumL1 + mask. That's okay.
-
For the second half, we also generate all combinations and for each compute its (d1, d2) and sumL2. Then for each, look up in the first half map for key (-d1, -d2). If exists, compute total = best_sumL1 + sumL2. Keep track of the maximum total and the masks (mask1, mask2) that achieve it.
-
At the end, if we found at least one match, we reconstruct the sequence of choices using mask1 and mask2. Then output the pairs accordingly.
But careful: The order of tasks: first half tasks are first n1 tasks; second half tasks are the remaining. So we need to output choices in order.
Encoding mask: For each task, we assign a code for the chosen pair: e.g., 0 for LM, 1 for LW, 2 for MW. Then for a half of length k, we can encode as a base-3 number or just use integer where bits 2 bits per task? Since 3 options, we can use base-3 representation. For k=13, 3^13 = 1,594,323, which fits in integer. In Python we can simply use a tuple of choices or store as integer. But storing as integer might be easier: encode as a number where each digit (0..2) is the choice. For example, for i from 0 to k-1, choice = (mask // (3**i)) % 3. For generation we can also use nested loops or recursion that builds the mask.
Better: Since we generate all combinations via recursion (or iterative enumeration using base-3 counter), we can keep a list of current choices for that half. When we add an entry to map, we need to record the choices as a mask (which we can construct incrementally). We can simply compute mask = encode(choices) as integer base-3.
Alternatively, we could store the list of choices (tuple) directly. For 500k entries, storing a tuple of length up to 12 might be memory heavy but acceptable? 531k entries each with a tuple of 12 ints ~ maybe 531k * 12 * 28 bytes = ~178 MB? That's too high. So better to encode as integer.
We'll implement: For first half length n1, we have an array
choices_firstof length n1; we compute mask as a base-3 number: mask = sum(choice_i * (3i)). That is unique and can be decoded later. Since n1 <= 13, 313 fits within 1.6 million, which is fine. But careful: 313 = 1594323, but the mask integer can be up to (3n1 -1) which is < 2 million, small.For second half length n2, similarly we encode mask2.
But we need to decode: For each task index i (0-based overall), we need to output two letters. For first half tasks indices 0..n1-1: decode mask1 to get choice code. For second half tasks indices n1..n-1: decode mask2.
Implementation details:
We'll have input n, and list of tasks: each a triple (l, m, w).
Define functions to compute Δ for each choice:
If choice == 0: LM -> (l, m, 0) choice == 1: LW -> (l, 0, w) choice == 2: MW -> (0, m, w)
We'll compute sumL, sumM, sumW incrementally.
But we only need differences d1 = sumL - sumM, d2 = sumL - sumW, and sumL.
So for each task, given choice, we can update:
if choice == 0: d1 += l - m; d2 += l - 0 = l? Wait d2 = sumL - sumW, so if sumW unchanged, d2 += l; sumL += l. But careful: For d1: sumL - sumM; for LM, sumL += l, sumM += m, so d1 change = l - m. For d2: sumL - sumW; sumW unchanged, so d2 change = l. Similarly:
- LW: sumL += l, sumW += w, sumM unchanged. So d1 change = l - 0 = l; d2 change = l - w.
- MW: sumL unchanged, sumM += m, sumW += w. So d1 change = 0 - m = -m; d2 change = 0 - w = -w.
Thus we can compute d1, d2 and sumL directly.
We'll generate combinations recursively.
Pseudo:
tasks = list of (l,m,w)
n1 = n // 2 (floor) or we could set n1 = min(15, n) but typical split. We'll compute n1 = n // 2, n2 = n - n1.
Define a recursive function gen(half_tasks, idx, cur_d1, cur_d2, cur_sumL, mask, results_map, is_first_half, store mask).
But we need to store into map only for first half; for second half we will iterate and lookup.
Simplify: Write a function
enumerate_half(start_idx, end_idx)that returns a list of tuples (d1,d2,sumL,mask) for that half? But for first half we want a map; for second half we want to iterate through list. Since sizes up to 3^13 ~ 1.6M, storing list for second half is okay (each tuple of 3 ints + mask). Memory: 1.6M * (3 ints + mask) ~ 1.6M * 4 * 28 bytes? Actually Python objects overhead is large. Better to not store all second half combos at once if we can process on the fly: we can generate second half combinations and for each, lookup in first map and update best total and masks. That would be more memory efficient, and we don't need to store second half combos all at once. So we will:-
First, generate first half combos and build map: dict where key = (d1,d2) -> (max_sumL, mask) (only keep best sumL for that key). If two combos have same d1,d2 and same sumL, we keep one arbitrarily.
-
Then, generate second half combos. For each, compute d1, d2, sumL, mask. Compute needed key = (-d1, -d2). If exists in map, compute total = map[need_key][0] + sumL. If total > best_total, update best_total, best_mask1 = map[need_key][1], best_mask2 = mask.
After scanning all second half combos, if best_total found (maybe we need to check if any match), then reconstruct.
Now, we need to pay attention to the case where both halves are empty? n can be 1, so n1 could be 0? If n1 = 0, first half has no tasks, we need to handle. Similarly n2 could be 0? If n is even, both halves non-zero? Actually n could be 1: n1 = 0, n2 = 1. Then first half has no tasks: there is exactly one combination: d1=0, d2=0, sumL=0, mask=0. We should include that in map. So we need to generate first half even if empty: map with key (0,0) -> (0,0). Similarly, if n1=0, then the first half map contains only that entry. So our generation function should handle zero tasks.
If n2 = 0 (n=0 not possible because n>=1). For n=1, n1 = 0, n2 =1. That's fine.
Now, need to generate combos for half with possibly up to 13 tasks. 3^13 = 1,594,323, which is manageable for recursion/iteration in Python. But we need to be careful with time: generating all combos for both halves total maybe ~2.4 million, each performing simple arithmetic, which should be fine within seconds.
Implementation details for generation:
We can use recursion with depth up to 13. Or we can use iterative base-3 counting. Since the number of combos is not huge, recursion is simpler. But we need to be careful about recursion depth (max 13) which is fine.
We'll define a function
gen(idx, end, cur_d1, cur_d2, cur_sumL, mask)that goes through tasks from idx to end-1 (the tasks of this half). At each step, for each option (0,1,2) we call recursively. When idx == end, we record the result.But we need to pass mask encoding: we can compute mask as we go, with base-3 digit for each position. If we treat tasks in order from first of half to last, we can set mask = mask3 + choice, or we can accumulate with power. To decode later, we need to know order. Using mask = sum(choice_i * (3**i)), where i is position from 0 to k-1 (the i-th task in that half). That would be easier if we build as we go: when we go deeper, we multiply the digit weight accordingly. However, recursion depth first, we could pass an accumulating mask where each level multiplies by 3 and adds choice, but then the most significant digit corresponds to first task? Actually if we build mask = mask3 + choice, then when we later decode, we would need to reverse the order (pop from least significant). That's fine, as long as we keep consistent. Let's define that the order of tasks in the half is from first to last (original order). Suppose half tasks indices: start...end-1. In recursion, at depth corresponding to task i (starting from first), we will have choices for tasks in order. So if we build mask = mask * 3 + choice, then the first task's choice becomes the most significant digit in base-3 representation. For decoding, we can retrieve choices by iterating from last to first: we can reverse the order by using while mask>0: digit = mask%3; mask//=3, then reversed list. But then the order of digits in the list will be from last task to first. So to output original order, we need to reverse that reversed list. That's fine. Or we can build mask as sum(choice_i * (3i)) with i as position from 0 (first) to k-1. That would be direct: to decode, we can extract digit_i = (mask // (3i)) % 3. But we need to compute powers of 3 up to n2 which is small. Both are fine. Let's choose the cumulative mask = mask*3 + choice. It's easier to compute during recursion. Then after finishing, mask will be an integer uniquely representing the sequence (since order is preserved: first digit most significant). For decoding, we can store the mask and later decode by repeatedly taking modulo 3 after reversing or by converting to base-3 string of length k. Since k <= 13, we can simply compute an array of choices by iterating from the end: for i in range(k-1, -1, -1): digit = mask % 3; mask //= 3; store in array[i] (since we are going backwards, we need to store from last to first, but we can just fill reversed and then reverse). Another way: we can compute choices as: for i in range(k): digit = (mask // (3**(k-1-i))) % 3. That requires precomputed powers. Simpler: we can store the mask and also store the list of choices as a tuple? But that increases memory. We can decode on demand later: given mask and k, we can reconstruct list of choices by repeatedly dividing and then reverse. That's cheap.
Thus for first half, we store mask (int). For reconstruction, we will decode both masks.
But careful: For first half of length n1, we have mask1 built as described (most significant digit first). For second half mask2 similarly (length n2). Then overall output: for i in 0..n1-1, we need to extract the choice for that task; similarly for i in n1..n-1. We'll decode mask1 and mask2 into lists choices1 and choices2 of lengths n1 and n2 respectively, preserving order.
To decode mask1 with length n1: we can get a list by:
def decode(mask, k): choices = [] for _ in range(k): choices.append(mask % 3) mask //= 3 # Now choices is from last task to first (reverse order) because we took least significant digit first. # So we need to reverse it to get original order. choices.reverse() return choices
But note: if we built mask by mask = mask*3 + choice in forward order, then the least significant digit corresponds to the last task. So this method yields reversed list; after reverse we get correct order.
Alternatively, we can use while mask>0 but for k maybe less than max length (if mask has leading zeros? Actually if the first few choices are 0, then mask may have fewer digits than k when we use division? For example, if k=2 and choices are [0,1], then mask = 03+0? Wait let's test: start mask=0; for first task choice=0 => mask = 03+0 = 0; for second task choice=1 => mask = 0*3+1 = 1. So final mask=1. That's not a k-digit base-3 number with leading zeros. If we decode by repeated modulo, we get digits for only the non-leading zeros? For k=2, we expect choices [0,1]. But mask=1 gives digits: first modulo = 1 (last task), then mask becomes 0, next modulo would be 0? Actually if we do for _ in range(k): digit = mask%3; mask//=3; then we will get exactly k digits, but if mask has fewer digits (i.e., leading zeros), the division will eventually produce 0 and we will get zeros for the earlier digits. But careful: after first iteration, mask becomes 0; second iteration digit=0, mask=0. So we get digits [1,0] which reversed gives [0,1] as desired. So it's fine: the loop always runs k times, taking digits from least significant to most, and if mask becomes zero early, subsequent digits are zero. This works because we always extract k digits. So decoding method is fine.
Edge cases: mask is an integer. For first half with zero tasks, k=0, mask should be 0 and decode yields empty list.
Now, generating combinations:
We'll define a recursive function
gen_first(idx, d1, d2, sumL, mask)where idx runs from 0 to n1-1 (if n1>0). For each choice, we compute new values and call gen_first(idx+1, ...). At the end (idx == n1), we update map.But we also need to consider that we may have multiple combos with same (d1,d2) but we want only the one with max sumL. So we store in a dict: key = (d1,d2) -> (sumL, mask). When inserting, if key not present or sumL > stored sumL, update.
Important: The map for first half should contain only the best sumL for each (d1,d2). However, is it possible that a combination with lower sumL but same (d1,d2) could produce a higher total when combined with some second half? No, because total = sumL1 + sumL2; for a fixed second half sumL2, the total is maximized by taking the highest sumL1 for the matching key. So keeping only max sumL1 for each key is safe.
But what about ties where sumL1 is same but we might later need to reconstruct differently? Not needed; any with max sumL works. Also note that there might be multiple combos with same max sumL; we can keep any.
Now for second half generation, we will call
gen_second(idx, d1, d2, sumL, mask)where idx runs from n1 to n-1 (or we can generate from 0 to n2-1 using separate list). We'll need to iterate over tasks of second half (indices n1..n-1). So we can store them in a separate arraysecond_tasks. Then generate combos similarly (recursively). For each combination, compute need = (-d1, -d2). Look up in first map. If found, compute total = first_sumL + sumL. Keep track of best total and the masks that achieved it.One nuance: The objective is to maximize the resulting attitude T = total sumL = sumL1 + sumL2. But is sumL indeed the common attitude? Since we require S_L = S_M = S_W = T. Our sumL1+sumL2 = total sum for L. That equals T. So maximizing T is equivalent to maximizing total sumL.
But is there any alternative? For completeness, we could also consider maximizing S_M or S_W but they all equal. So sumL is fine.
Edge case: The final T might be negative. But the problem likely expects maximum possible (could be negative). The statement: "choose the one in which the value of resulting attitude is greatest possible." That could be negative if all possibilities lead to negative. So we need to consider that. Our maximization should handle that. However, we need to ensure we have a solution. If no match, output Impossible.
Now, consider the possibility that the first half has many combos, up to 3^13 ~ 1.6M. The dictionary mapping from (d1,d2) to best sumL will have at most that many entries. But in practice many keys may collide. This is okay memory wise; but we must ensure we use efficient data structures. Python dict with tuple keys is fine for 1.6M entries? That's a bit large but might be borderline for memory. Each entry overhead: tuple of two ints (object overhead) plus dict entry overhead. 1.6M entries could be maybe a few hundred MB. That's too high. We need to reduce memory usage. Since n <= 25, maybe we can choose n1 = 13, n2 = 12, but 3^13 = 1.6M; storing all combos in a dict might be heavy but possibly still within memory limits? Let's estimate: Each dict entry has key tuple (2 ints) and value tuple (2 ints: sumL and mask) plus dict overhead. Rough estimate: In Python, an int object is about 28 bytes (for small ints maybe less? But Python ints are objects, 28 bytes each). A tuple of 2 ints would contain references to two ints. The tuple itself is ~56 bytes? Actually typical: empty tuple 56? Not sure. Let's approximate: Each int ~28 bytes, each tuple ~56 bytes? That would be ~140 bytes per entry just for key and value objects, plus dict overhead (72 bytes per entry?). So total maybe >200 MB for 1.6M entries, which is too high. So we need a more memory-efficient approach.
We can compress by using hashing with a single 64-bit integer key? Since d1 and d2 can be up to about 1.3e8, they can be combined into a single 64-bit integer: key = (d1 << 32) | (d2 & 0xffffffff) assuming d1,d2 within 32-bit signed? They could be up to around +/- 2.5e8, which fits in 32-bit signed (range -2.5e8 to 2.5e8). Actually 2.5e8 < 2^31, so fits in 32-bit signed. But we must handle negative numbers; we can offset to unsigned. Python ints are arbitrary precision, but we can combine into a tuple (d1,d2) anyway; but memory is the issue. Perhaps we can use a dictionary mapping from a 64-bit integer key to a tuple of (max_sumL, mask). This reduces the tuple overhead? In Python, a single int key is still an object, but it's only one int instead of a tuple of two ints. However, the int may be large but still one object. So memory might be less: one int (28 bytes) vs tuple (56 bytes + 2 ints). Actually the tuple contains references to ints, and those ints are separate objects; so key as a tuple would have three objects: tuple, d1 int, d2 int. Key as a combined int would be just one int. That's a big saving. So we can combine d1 and d2 into a single 64-bit integer: key = (d1 + offset) << 32 | (d2 + offset) where offset is some constant to make them non-negative. However, d1,d2 may be negative, but we can map to unsigned by adding a big constant? The range of d1,d2: maximum absolute sum per half: each value li, mi, wi up to 1e7, n up to 13. So sum of differences: d1 = sum of (l-m) or l or -m, etc. The maximum absolute value per half: each term can be up to 1e7 - (-1e7) = 2e7? Actually l_i, m_i, w_i each up to 1e7 in absolute. So l_i - m_i could be up to 2e7, and l_i could be up to 1e7, -m_i up to 1e7. So each d1 increment per task is in range [-2e7, 2e7]? But sum of up to 13 gives up to 260 million. That's within 2^31. So we can offset by, say, 3e8 to make positive. But we need to combine into a single 64-bit integer. In Python, we can compute key = (d1 << 32) ^ (d2) or pack: key = (d1 + OFFSET) << 32 | (d2 + OFFSET). However, Python ints are arbitrary precision, but we can just pack as a tuple for simplicity; but memory is the main issue.
But perhaps we can use a dictionary with two-level: map d1 to dict of d2->(sumL, mask). That would still store many ints but maybe less overhead? Actually each inner dict also adds overhead. Not great.
Alternative: we can use a hashmap that stores pairs as keys but we can also use the fact that 3^13=1.6M, but we might not need to store all if we compress? But we need to store one best per (d1,d2). However many combos will have distinct (d1,d2) but likely many collisions? Possibly number of distinct (d1,d2) could be up to 1.6M as well, but maybe less. However worst-case could be close to 1.6M if differences are random. That's risky.
We can instead use meet-in-the-middle approach but with n1=12 and n2=13? Actually 3^12 = 531441, which is much smaller. So if we make first half smaller (e.g., 12) and second half larger (13), then the map for first half would have at most 531k entries. That's more manageable. 531k entries, each key as a tuple (d1,d2) might be okay? Let's approximate: 531k * (tuple + two ints + value tuple + dict overhead) ~ maybe 100-150 MB? Possibly still high but maybe within typical contest memory (256 MB?). Python overhead might cause memory exceed. Better to use combined int for key and store value as a single integer encoding both sumL and mask? Or store sumL and mask as two separate ints in a tuple. But we can pack sumL and mask into a 64-bit integer as well? However sumL can be up to 1.2e8, mask up to 3^12 ~ 531k, so we can pack into a 64-bit: e.g., (sumL << 20) | mask? But sumL may be negative. So we would need to offset sumL. But easier: we can store as tuple (sumL, mask). That's two ints. But the overhead of tuple might be okay for 531k entries? Each entry: key (int), value (tuple of 2 ints). The key is an int (28 bytes), the tuple is about 56 bytes plus two ints (2*28) = 56+56=112, plus dict entry overhead (~72 bytes?), total maybe ~212 bytes per entry * 531k = ~112 MB. Might be acceptable? Possibly near limit but maybe okay. However, we also have recursion overhead and other structures. But we can reduce further: we can store for each key only the sumL and mask as two separate ints but we could store them as a single 64-bit integer by encoding sumL in high bits and mask in low bits. Since sumL may be negative, we can add a large constant to make it non-negative. For example, sumL range: worst-case for n=12, each l_i up to 1e7, sumL up to 1.2e8, but could also be negative down to -1.2e8. So we can offset by OFFSET_SUM = 2e8. Then sumL_adj = sumL + OFFSET_SUM fits in 30 bits (since 4e8 < 2^29). Mask up to 531441 < 2^20. So we can pack into a 64-bit: combined = (sumL_adj << 20) | mask. Then store as a single int for value. This reduces value to one int. Then the dict entry would have key (int) and value (int). That's quite memory efficient. We'll need to decode later: from combined, we can extract mask = combined & ((1<<20)-1), sumL_adj = combined >> 20, sumL = sumL_adj - OFFSET_SUM. That's fine.
We also need to store mask for first half (max 531441) and sumL. This packing works.
Alternatively, we could store the best sumL and mask separately but as two ints in a list? Still overhead.
We'll implement packing.
Now for first half length n1 = min(12, n // 2?) Actually we can decide: we want first half to be the smaller half to reduce map size. So let n1 = n // 2 if n is even, else floor? For n=25, n//2 = 12, n2=13. That's good. For n=24, n1=12, n2=12. For n=23, n1=11, n2=12. So first half is at most 12. That's fine.
Thus n1 = n // 2 (floor), n2 = n - n1.
Now generate first half combos for indices 0..n1-1.
Pseudo:
first_tasks = tasks[:n1] first_map = dict() # key: combined_diff (int) -> packed_value (int) containing (sumL_adj << 20) | mask
OFFSET_DIFF = 300000000 # safe offset for d1,d2? Actually we will combine d1,d2 into a 64-bit key. We'll use 64-bit packing: (d1 + OFFSET) << 32 | (d2 + OFFSET). Since d1,d2 range about +/- 2.6e8, we need OFFSET >= 3e8 to ensure positive. We'll choose OFFSET = 400000000 to be safe (since 2.6e8+ offset still within 32 bits). Actually 400 million = 4e8, fits in 32 bits? 4e8 < 2^32 (~4.29e9). So okay.
But note: When combining two ints into one, we need to ensure the result is hashable (int is). So we compute key = ((d1 + OFFSET) << 32) | (d2 + OFFSET). This will produce an integer that is unique for each pair within range.
Alternative: we can use tuple for key but use packing for memory. We'll pack.
Define OFFSET_DIFF = 400_000_000 (or maybe 500_000_000 to be safe, but must fit in 32 bits). Actually maximum absolute sum for half of 12 tasks: each term could be up to 1e7 for l, so sumL up to 1.2e8, but d1 = sumL - sumM, which could be as high as each task's difference up to 2e7 (if l and m opposite signs) so sum difference up to 2.4e8? Actually absolute max: l_i = 1e7, m_i = -1e7 => l_i - m_i = 2e7. So for 12 tasks, d1 could be up to 2.4e8. Similarly negative down to -2.4e8. So offset 300 million is safe. But we might as well choose 400 million to be safe.
Now for packing sumL: sumL range: each l_i up to 1e7, sum up to 1.2e8, could be negative -1.2e8. So offset sum maybe 200 million. But we can use same offset 400 million? That would require more bits. But we have 64 bits; we can allocate 40 bits for sumL_adj? Since sumL_adj = sumL + OFFSET_SUM. If OFFSET_SUM = 200 million, sumL_adj up to 320 million, fits in 29 bits (2^29 = 536 million). Actually 320 million < 2^29. So 29 bits. Mask up to 3^12 ~ 531441 < 2^20. So we can allocate 30 bits for sumL_adj and 20 bits for mask. So combined fits in 50 bits. So we can use separate offsets.
Thus we define:
OFFSET_DIFF = 300_000_000 # for d1,d2 OFFSET_SUM = 200_000_000 # for sumL
But we must ensure OFFSET_DIFF and OFFSET_SUM are enough for worst-case values. n can be up to 25, but we are only using halves. For first half with n1=12, maximum absolute d1 = sum of absolute differences per task. Each task: max |l_i - m_i| could be 2e7. So up to 2.4e8. So OFFSET_DIFF=300e6 works. For second half n2 up to 13, similar. So safe.
For sumL: up to 1.2e8, so offset 200e6 works.
Now, generate first half combos:
We'll define recursive function:
def dfs_first(idx, d1, d2, sumL, mask): if idx == n1: key = ((d1 + OFFSET_DIFF) << 32) | (d2 + OFFSET_DIFF) packed = ((sumL + OFFSET_SUM) << 20) | mask # If key not in map or packed's sumL > existing sumL, update if key not in first_map: first_map[key] = packed else: existing = first_map[key] existing_sumL = (existing >> 20) - OFFSET_SUM if sumL > existing_sumL: first_map[key] = packed return l,m,w = first_tasks[idx] # Option 0: LM dfs_first(idx+1, d1 + (l - m), d2 + l, sumL + l, mask3 + 0) # Option 1: LW dfs_first(idx+1, d1 + l, d2 + (l - w), sumL + l, mask3 + 1) # Option 2: MW dfs_first(idx+1, d1 - m, d2 - w, sumL, mask*3 + 2)
But careful: For option MW: sumL unchanged, d1 = sumL - sumM, with sumL unchanged, sumM increased by m, sumW increased by w, so d1 decreases by m, d2 decreases by w. Yes.
Check for option LM: d2 change = l (since sumW unchanged) correct. Option LW: d1 change = l (since sumM unchanged) correct? Actually for LW: sumL increases by l, sumM unchanged, sumW increases by w. So d1 = sumL - sumM increases by l; d2 = sumL - sumW: increase by l - w. So d2 change = l - w. Good.
Option MW: sumL unchanged, sumM increases by m, sumW increases by w. So d1 changes by -m, d2 changes by -w. Good.
Now for second half: tasks indices n1 to n-1, we will have second_tasks list. We'll generate similarly, but with n2 length. For each combo, compute d1, d2, sumL, mask. Compute need_key = ((-d1) + OFFSET_DIFF) << 32 | ((-d2) + OFFSET_DIFF) (i.e., key for first half needed). But careful: d1,d2 from second half are for that half. The needed first half differences should be -d1, -d2. So we compute need_d1 = -d1, need_d2 = -d2. Then need_key = ((need_d1 + OFFSET_DIFF) << 32) | (need_d2 + OFFSET_DIFF). Check overflow? Since we add offset, it's fine.
Then if need_key in first_map, unpack first_sumL and first_mask. Compute total = first_sumL + sumL. If total > best_total (initialized to -inf), update best_total, best_masks = (first_mask, mask).
We also need to handle the case where the best total is negative: we might get total = -100. That's fine; we need maximum possible. But we must initialize best_total to something like -10**18 (or None). If we never find a match, output Impossible.
After scanning all second half combos, we reconstruct.
But careful: For second half, the mask built similarly (mask*3 + choice) as we go. But note: The order of tasks in second half is from index n1 to n-1. That's consistent with the recursion order: first call for first task of second half (index 0 within second half) corresponds to original task n1. So mask built that way will encode the choices for second half in order. So decode accordingly.
Now, potential pitfalls: When n1 = 0, the first half map should contain one entry: d1=0,d2=0,sumL=0,mask=0. So we need to generate that. In dfs_first, if n1 == 0, we should directly insert. We can handle by checking before recursion: if n1 == 0: we call the insertion function directly with values 0,0,0,0. Or we can set first_map = {} and then add manually.
Similarly for n2 = 0, second half generation will have no combos; but we can handle by if n2 == 0: we still need to consider the case where only first half exists. But n>=1, so n2 will be at least 1 if n1=0? For n=1, n1=0, n2=1. So second half generation will produce combos and we combine with first half's single entry. Good.
Now, complexity: 3^{n1} up to 531,441, which is fine. 3^{n2} up to 3^{13}=1,594,323, which is also okay to iterate recursively (about 1.6 million). Recursion depth up to 13, safe. But we need to ensure recursion doesn't cause stack overflow? Python recursion depth default is 1000, so fine. But recursion for 1.6 million calls may be okay if implemented efficiently? Actually each leaf of recursion corresponds to one combination, and the recursion explores all combinations using depth-first. The number of nodes visited is about 1 + 3 + 3^2 + ... + 3^{13} = (3^{14}-1)/(3-1) ~ 2.3 million, which is okay. But recursion overhead in Python for 1.6 million leaf calls might be okay? However, using recursion for each combination may cause a lot of function calls. We can implement iterative loops using product from itertools? That would generate all combos as tuples and iterate, but that would also create many tuples, memory heavy. Recursion with a function that calls itself may be okay. But we have to be careful with speed: 2.3 million recursive calls is fine. However, we also have to compute d1,d2,sumL updates and pack into map etc. This should be okay within time (maybe 1 sec). But we need to be careful with Python overhead: 2 million recursion calls is okay, but 1.6 million for second half plus 0.5 million for first half, plus map lookups, should be okay.
But there is a nuance: In the second half recursion, for each leaf we do a dict lookup. That's also fine.
Potential memory: first_map may have up to 531k entries, each with a key (int) and value (int). That's fine. second half we don't store all combos.
Now, we also need to handle the case where there are multiple matches for same key in first half but we only stored the best sumL. But is it possible that a combination with lower sumL1 but same (d1,d2) could yield a higher total when combined with a second half that also has higher sumL2? But we are scanning second half combos and for each we get sumL2 fixed; the total = sumL1 + sumL2. So to maximize total for that specific second half combo, we want the maximum sumL1 among those with the matching key. So storing max sumL1 is optimal.
But there is a subtlety: What if there are two first half combos with same (d1,d2) but different masks, and both have the same max sumL1? We can keep any; it doesn't matter for maximizing total. But we need to reconstruct some valid solution; any works.
Now, after we find best_total and best masks, we need to reconstruct the choices and output the pairs. For each task, based on choice code (0,1,2), output the corresponding string: 0 -> "LM", 1 -> "LW", 2 -> "MW". However note: The problem's output requires two characters in any order (but likely they want the exact pair? The examples show LM, MW, etc. They are in uppercase letters. They may accept any order? Usually they want the two letters, order doesn't matter as long as they are the correct two companions. So we can output "LM" or "ML"? The problem says "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". So we can output e.g., "LM" or "ML". For simplicity we output the order consistent with our encoding: 0 -> LM, 1 -> LW, 2 -> MW.
But check: For option LW, we output "LW" (or "WL")? We'll output "LW". The examples used LM, MW, etc. So that's fine.
Now, we need to ensure we output exactly n lines.
Edge Cases: The numbers could be large up to 1e7, but sums within int.
Now, possible pitfalls: The meet-in-the-middle approach as described should work. However, we need to consider that the differences d1,d2 and sumL can be negative, so we need to apply offsets when packing. But we must ensure that when we compute need_key for second half, we compute with -d1 and -d2 and add offset. Since offset is added, the key for first half with (x,y) is ((x+OFFSET)<<32) | (y+OFFSET). So for need_key we compute the same.
Now, we must ensure that the offset is large enough so that x+OFFSET is non-negative and fits in 32 bits. Since x can be as low as -max_d. With offset 400,000,000, x+offset is at least 400e6 - 260e6 = 140e6 > 0, and at most 400e6+260e6=660e6 < 2^31 (2.147B). So fits in 32 bits. So shifting left 32 bits and OR-ing is safe in Python (no overflow issues).
Now, packing for first map value: sumL_adj = sumL + OFFSET_SUM, where OFFSET_SUM we choose maybe 200,000,000. sumL could be as low as -120e6, so sumL_adj >= 80e6 >0, and up to 320e6. So 30 bits. We'll shift left by 20 bits and OR mask (mask < 3^n1 <= 3^12 = 531441 < 2^20). So sumL_adj << 20 fits within about 50 bits. Python int fine.
Now, we need to compute mask for first half and second half. But note: For first half, mask is a number representing the choices in that half (base-3 digits). The maximum mask for n1=12 is 3^12 -1 = 531440, which is < 2^20 (1,048,576). So mask fits into 20 bits. For n2=13, mask max = 3^13 -1 = 1594322, which is < 2^21 (2,097,152). But we only need to store mask for second half when we find best; we don't pack it. So that's fine.
Now, one more nuance: The first map stores only one combination per (d1,d2) with maximum sumL. However, is it guaranteed that we can reconstruct the full solution? We store the mask for that best sumL. When we later find a second half combination that matches, we use the stored mask. That works because we stored the mask for that best sumL. However, there could be multiple first half combos with same (d1,d2) and same max sumL, we keep one. That's fine.
Now, we must consider that the best total overall might be achieved by a combination where first half's sumL is not the maximum for its (d1,d2). But is that possible? Suppose we have two first half combos with same (d1,d2) but different sumL: A has sumL=10, B has sumL=5. For a given second half combo with sumL2=100, total from A=110, from B=105. So A is better. For a second half combo with sumL2=0, total from A=10, B=5 => A better. For any sumL2, A gives higher total. So max sumL1 always gives better or equal total regardless of sumL2. So storing only max sumL1 is sufficient.
Now, we should also consider that there might be multiple second half combos with same (d1,d2) and we are looking for max total; we are scanning all second half combos, so we will consider each and compute total with the stored best first half. That yields the best total because for each second half combo we pair it with the best first half for that key. Since any global optimum consists of some first half combo F and second half combo S. For that key K = (d1_F, d2_F), we have stored some first half combo F' with same key and sumL1' >= sumL1_F. Then total' = sumL1' + sumL2_S >= sumL1_F + sumL2_S = optimum total. So optimum total cannot be higher than the maximum we find. Since we consider all second half combos, and for each we have the best first half for that key, the maximum total we find is at least as high as the true optimum. But could it be higher than any feasible combination? No, because F' and S together also satisfy the difference condition? Wait, if F' has same (d1,d2) as F, then d1_F' = d1_F, d2_F' = d2_F. Then for S with (d1_S, d2_S) we need d1_F + d1_S = 0 and d2_F + d2_S = 0 for feasibility. If (F,S) is feasible, then d1_S = -d1_F, d2_S = -d2_F. So for S, its (d1_S, d2_S) = (-d1_F, -d2_F). Then for F' with the same key as F, we also have d1_F' = d1_F, d2_F' = d2_F, so d1_F' + d1_S = 0, d2_F' + d2_S = 0, so (F', S) is also feasible. So the combination (F', S) is valid and yields total sumL1' + sumL2_S which is >= original total. So the optimal total will be found because we consider