Snowballs in a Tilting Trough

A long trough is divided into slots. Each slot holds a snowball of some size (a positive integer) or is empty (0). When the trough is tilted, every snowball slides as far as it can toward the low end. While sliding, two snowballs of equal size that meet merge into one snowball of twice the size. A snowball created by a merge cannot merge again during the same tilt, and merging happens starting from the low end: the snowball nearest the low end merges first.

You are given row (a list of integers) and tilts, a string of "L" (the left end is low) and "R" (the right end is low) characters, applied in order. Write tilt_trough(row, tilts) that returns the row after all tilts, as a new list of the same length with 0 for empty slots. Do not change the list you were given.

Examples

Input:  row = [2, 0, 2, 4], tilts = "L"
Output: [4, 4, 0, 0]
Explanation: the two 2s merge into a 4; that new 4 may not merge with the old 4.

Input:  row = [2, 2, 2, 0], tilts = "R"
Output: [0, 0, 2, 4]
Explanation: the right end is low, so the two rightmost 2s merge first.

Input:  row = [2, 2, 4, 8], tilts = "LL"
Output: [8, 8, 0, 0]
Explanation: the first tilt gives [4, 4, 8, 0]. In the second tilt the two 4s merge into an 8,
which may not merge with the old 8 during that same tilt.

Constraints

• 0 <= len(row) <= 200, every entry is 0 or a power of two up to 2**20
• 0 <= len(tilts) <= 200

Goals

• Compact a list by dropping the empty slots
• Merge neighbours so that each item merges at most once
• Reuse one routine for both directions by reversing the list