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.

ios_base::sync_with_stdio(false);
cin.tie(NULL);

To understand more about what they do, you can read Fast I/O for Competitive Programming

Credits to Vinayak Sangar for the above.