Decode the XOR Chain

A secret list perm holds the numbers 1, 2, ..., n in some order, each exactly once, and n is odd. Instead of the list itself you were given encoded, where encoded[i] is perm[i] ^ perm[i + 1], the bitwise XOR of two neighbours. So encoded has n - 1 numbers.

Write decode_permutation(encoded) that returns the secret list perm. There is always exactly one answer.

Examples

decode_permutation([3, 1])          # returns [1, 2, 3]
decode_permutation([6, 5, 4, 6])    # returns [2, 4, 1, 5, 3]
decode_permutation([6, 2, 3, 6])    # returns [5, 3, 1, 2, 4]

In the first example, 1 ^ 2 = 3 and 2 ^ 3 = 1, which is exactly encoded.

Constraints

• n = len(encoded) + 1 is odd, and 1 <= n < 100,000
• encoded always comes from a real arrangement of 1 to n