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.