There is a hidden integer array arr containing $n$ elements that was transformed into an array encoded of length $n - 1$ such that encoded[i] = arr[i] ^ arr[i + 1] for all valid indices $i$.

Given the integer array encoded and an integer first representing the initial element arr[0], reconstruct and return the original array arr.

Constraints:

• $2 \le n \le 10^4$

• encoded.length $== n - 1$

• $0 \le$ encoded[i] $\le 10^5$

• $0 \le$ first $\le 10^5$

Input: encoded = [0]-List[int], first = 50000-int
Output: [50000,50000]-List[int]
Explanation: Starting with 50000, the next value is 50000 ^ 0 = 50000, reconstructing the array [50000,50000].

Input: encoded = [12,5,9,2]-List[int], first = 7-int
Output: [7,11,14,7,5]-List[int]
Explanation: Starting with 7, each subsequent value is obtained by XORing the previous value with the corresponding encoded value: 7 ^ 12 = 11, 11 ^ 5 = 14, 14 ^ 9 = 7, and 7 ^ 2 = 5.

Input: encoded = [100000,0,65535]-List[int], first = 100000-int
Output: [100000,0,0,65535]-List[int]
Explanation: Starting with 100000, the reconstructed values are 100000 ^ 100000 = 0, 0 ^ 0 = 0, and 0 ^ 65535 = 65535.

Input: encoded = [31,63,1,127,8]-List[int], first = 42-int
Output: [42,53,10,11,116,124]-List[int]
Explanation: Starting with 42, each subsequent value is reconstructed by XORing the previous value with the next encoded value: 42 ^ 31 = 53, 53 ^ 63 = 10, 10 ^ 1 = 11, 11 ^ 127 = 116, and 116 ^ 8 = 124.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.