In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the following binary tree:
(source: Dutch Olympiad in Informatics, finals, 2012/13)
can be represented in prefix notation as
abrxdbe, in infix as
rbxabde and in postfix as
In this case, you are confronted with a complete binary tree represented in infix notation. Your task is to convert this tree to prefix notation. Your input on stdin will be 2n-1 lowercase alphabet characters, a-z and no more, ended with a newline character, for any integer n such that 1 ≤ n ≤ 16. Thus, the maximum number of characters you will get is 65535. Output the tree to stdout in the same way, but then in prefix format.
This is code golf, so the shortest code, counted in bytes, will win. Votes will act as a tie breaker, and if those tie up as well, submission date and time.