I guess you found out the mistake with the problemsetter's help. Now your code is giving TLE.
The reason is, that you do some unnecessary things in your algorithm. If you do some more analyses on the problem, you will be able to reduce and thus speed up your code. My AC solution runs in 0.22 s without any special speed up tricks just with a straight forward code after a proper analysis. The code you posted is about 20 times slower (run with some random data).