I tried to solve it with C++.  It was long.  It was PAINFUL!  Finally,  I didn't managed to solve it in C++.  And then I just opened my Python IDE and solves it within 10 minutes.  Just AC first attempt.  The task is evil.