Notes: This problem needs input-output optimization to run in time. If you are using C++ and you use cin to get your input, add these two lines to the beginning of the main function. You don't need to do anything if you use scanf.
To understand more about what they do, you can read Fast I/O for Competitive Programming
Credits to Vinayak Sangar for the above.