Solution by Nikhil Prasanna.