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.