At first, I tried to solve this problem with a persistent trie and a segment tree, but got a TLE. (Source Code)
Then, I replaced the segment tree with a sparse table, and do some other constant optimizations to turn the TLE into AC. (Source Code)
The time complexity of my solution is \mathcal O(n\log n+(n+q)\log v_i).
So, I wonder if there are solutions with lower time complexity, or we just need to reduce constant factors to fit the time limit.