Folded Stencil

A rectangular paper sheet is drawn as a list of equal-length strings sheet, one character per square. The ink soaks through, so each square shows the same character on both faces. The sheet lies flat on a table; rows and columns are always counted in the current (folded) sheet as seen from above, with row 0 at the top and column 0 at the left. Every position of the folded sheet holds a stack of one or more paper layers.

Each entry of folds is a string "S k" where k is a positive integer smaller than the current size in that direction:

• "L k": the k leftmost columns are lifted and folded over to the right along the line between column k-1 and column k. That line becomes the new left edge: old column k+j becomes new column j, and the flap's old column k-1-j lands on new column j. The new width is max(k, width - k), so a flap wider than the rest sticks out past the old right edge.
• "R k": the mirror image. The k rightmost columns fold over to the left, the fold line becomes the new right edge, and the new width is max(k, width - k).
• "U k": the k top rows fold down; the fold line becomes the new top edge; the new height is max(k, height - k).
• "D k": the k bottom rows fold up; the fold line becomes the new bottom edge; the new height is max(k, height - k).

A flap turns over as it folds, so it lands on top of whatever is already at its new position, and the order of its layers is reversed: at each position, the flap's lowest layer becomes the highest one.

After all folds, a needle is pushed through every layer at each position (r, c) in punches. Return a tuple (top, pierced):

• top: the folded sheet seen from above, as a list of strings: at each position, the character of the highest layer.
• pierced: the sheet unfolded back to its original shape, as a list of strings, with every pierced square replaced by *.

Examples

Input:  sheet = ["abc"], folds = ["L 1"], punches = [(0, 0)]
Output: (["ac"], ["**c"])
Explanation: column 0 folds onto column 1, so the new width is 2 and "a"
lies on top of "b". The needle at (0, 0) pierces both "b" and "a".

Input:  sheet = ["abcd",
                 "efgh",
                 "ijkl"], folds = ["R 1", "U 2"], punches = [(0, 2)]
Output: (["efg", "abc"], ["abcd", "ef**", "ij**"])
Explanation: after "R 1" the sheet is 3 wide and "d", "h", "l" lie on "c",
"g", "k". Then the top two rows fold down onto the last row and the sheet is
2 high. At new position (0, 2) the stack from bottom to top is k, l, h, g:
the old stack g, h was turned over, so g is now highest.

Constraints

• 1 <= len(sheet), len(sheet[0]) <= 30; the characters are lowercase letters or .
• 0 <= len(folds) <= 12, and every fold is valid for the current size
• 0 <= len(punches) <= 10; every punch is a valid position in the final folded sheet

Goals

• Apply reflections of a grid about a fold line, including flaps that overhang the edge
• Track the stack of paper layers at every position and how folding reverses it
• Map positions in the folded sheet back to squares of the original sheet