Tough to AC, but possible (finally I managed to do it). Since there can be up to 100000 queries, bottleneck is output as usual with Python. Don't use print - use sys.stdout.write() instead (interestingly, why you used sys.stdin for input and print for output?)
Looking at TLE times in testing queue is a misleading way to analyze your code effectiveness (actually, it shows time after which your code was halted with TLE verdict rather than acrtual running time). Test it locally on large tests and measure time efficiency of each alternative. Also, I see you submit on Python 3. That may be the problem - I ACed on Python 2.