A dragon curve is a repeated pattern that never intersects itself. You get a dragon curve of the order $$n$$ ($$n \geq 0$$) when a strip of paper is folded $$n$$ times in two and then unfolded so the folds form right angles. The name is based on the fact that the pattern is very similar to a certain mythical creature.

The instructions to draw a dragon curve can be written down as a string consisting only of the letters F, L and R. Here, the instruction F means "'draw a line while moving a step forward", the instruction L means "turn 90 degrees counterclockwise" and the instruction R means "turn 90 degrees clockwise". The key to writing down the instructions stems from the finding that a curve of the order $$n$$ is ($$n > 0$$) formed by a curve of the order $$ n-1 $$, followed by the letter L and the curve of order $$n-1$$, which is made in reverse order (reverse the string instructions, L replaced by R and R replaced by L). The curve of the order 0 consists simply of a string with a single instruction: F. The figure below shows the instructions to draw dragon curves of the order 0, 1, 2 and 3.

Assignment

1. Write a function dragoncurve that returns the string with instructions needed to draw a dragon curve of the order $$n$$ ($$n \ geq 0$$). The order $$n$$ should be passed to the function as argument. Imagine a Cartesian plane where the $$x$$-axis of the coordinate system is directed to the right, and the $$y$$-axis upwards. Suppose we are initially at the origin (0,0) with our noses in the direction of the positive $$x$$-axis. Now, if we execute the instruction F of a dragon curve, we arrive at the point (1,0). If we then execute the instruction L, we stand with our noses towards the positive $$y$$-axis. If we re-execute the instruction F, we arrive at the point (1,1).

2. Write a function curve2positons to which a string must be passed consisting only of the letters F, L and R, in accordance with the instructions that are used to draw a dragon curve. The string with instructions will not necessarily deliver a dragon curve. The function must return the list of positions (points in the Cartesian plane represented as tuples with length two) that are successively visited as the instructions from the given string are executed.

Example

>>> dragon curve(0)
'F'
>>> dragon curve(1)
'FLF'
>>> dragon curve(2)
'FLFLFRF'
>>> dragon curve(3)
'FLFLFRFLFLFRFRF'
>>> curve2positons('FLFLFRFLFLFRFRF')
[(0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (-1, 2), (-1, 1), (-2, 1), (-2, 2)]
>>> curve2positons('FFLRLFLRLFRFFFLF')
[(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)]
>>> curve2positons('LLLFRFLLFRRRFLRLF')
[(0, 0), (0, -1), (-1, -1), (0, -1), (0, 0), (-1, 0)]