I haven't idea how to speed up my program. Now it works about 1 sec locally on random tests, but still TLE #26. Queries caching doesn't help too.

Could somebody tell me some hints or even send correct q-tree solution, please? 1.5 years of futile attempts made me totally mad =) Maybe I miss sort of useful worst case heuristic...

My email is dkorduban [at] ukr [dot] net.