Here is my solution, https://www.codechef.com/viewsolution/12155819 well commented.
Link to setter’s solution is broken.