Given an array of n positive integers called a
For each of q queries which are described with integers 1 ≤ l ≤ r ≤ n, output xor of unique values in segment(l, r), i.e. if x₁, x₂, x₃, ..., x_k is set of unique values from a_l, a_l + 1, a_l + 2, ..., a_r - 2, a_r - 1, a_r, then output x₁ xor x₂ xor x₃ xor ... xor x_k

1 ≤ n, q ≤ 10⁶
for all i, 1 ≤ a_i ≤ 10⁹

TL: 3.5 seconds
ML: 256 megabytes

How to solve it?
If it's possible, I'd like a solution which uses some of data structures listed below:
Segment Tree
Binary Rise/Lift
Trie
Merge Sort Tree