it's sad that tests for problem 463E - Caisa и дерево are weak that many solutions with complexity O(n*q) passed the final system test... :(

here's a hack 7651095 for those solutions

and i test it local on my computer (about 3 times slower than cf machines... :(

it takes solution 7644844 191.45s.

it takes solution 7645960 2.55s. (my solution :)

it takes solution 7650771 0.20s. (so quick :)

their output are the same