My submission works in O(n logn logA) = 1.2*10^8. Its time limit is 8 seconds

Submission link: https://codeforces.net/contest/1777/submission/238628649

If we iterate on smaller segment then the query will run for nlogn times and trie works in log A