1370. Decode XOR Encoded Permutation

A permutation of the integers 1 through n, where n is odd, was encoded into an array of length n-1 with encoded[i] equal to perm[i] XOR perm[i+1]. Given the encoded array, reconstruct and return the original permutation.

Input: A JSON object {"encoded": [<integers>]} of length n-1 for an odd n.

Output: Return the original permutation of 1..n.

Examples

Input: {"encoded":[3,1]}
Output: [1,2,3]
Explanation: Recovering the first element gives the permutation [1,2,3].

Input: {"encoded":[6,5,4,6]}
Output: [2,4,1,5,3]
Explanation: The reconstruction yields [2,4,1,5,3].

Constraints

• 3 <= n < 10^5 and n is odd
• len(encoded) = n - 1

Asked by