You are given an integer array pref of length $n$.

Find and return the array arr of length $n$ that satisfies:

pref[$i$] = arr[$0$] ^ arr[$1$] ^ ... ^ arr[$i$]

for all indices $i$ such that $0 \leq i < n$, where ^ denotes the bitwise XOR operation.

Note: It can be proven that the resulting array arr is unique.

Constraints:

• $1 \leq$ pref.length $\leq 10^5$

• $0 \leq$ pref[i] $\leq 10^6$

Input: pref = [0]-List[int]
Output: [0]-List[int]
Explanation: The first element is arr[0] = pref[0], so the resulting array is [0].

Input: pref = [8,8,8,8]-List[int]
Output: [8,0,0,0]-List[int]
Explanation: The first element is 8, and each subsequent element is the XOR of consecutive prefix values: 8 ^ 8 = 0, resulting in [8, 0, 0, 0].

Input: pref = [1,3,7,2,10,4]-List[int]
Output: [1,2,4,5,8,14]-List[int]
Explanation: The first element is 1, and each subsequent element is obtained by XORing consecutive prefix values: 1, 3 ^ 1 = 2, 7 ^ 3 = 4, 2 ^ 7 = 5, 10 ^ 2 = 8, and 4 ^ 10 = 14.

Input: pref = [1000000,0,999999,524288]-List[int]
Output: [1000000,1000000,999999,475711]-List[int]
Explanation: The first element is 1000000, followed by the XORs of consecutive prefix values: 0 ^ 1000000 = 1000000, 999999 ^ 0 = 999999, and 524288 ^ 999999 = 475711.

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.