The problem is ACPC 2012 problem, called "No Name". http://mirror.codeforces.com/gym/100155/problem/B

The solution is to use a binary indexed tree/fenwick. A sample solution I found was here: http://ahmed-aly.com/f.jsp?i=p2lxbV2O&h

I understood what the solution is doing. Basically creating the final string first, and then sort of "hiding" everything, and then revealing them one-by-one as insertions are being made, so when asked to print, can print only from those who are "visible". I convinced myself that the second stage of printing the answers is correct, because assuming I got the final string correctly, none of the insertions change the order of the characters of each word, or the words relative to each other, so "hiding" later inserted words and printing from ones currently inserted should be okay.

However, I tried and couldn't formulate a solid argument regarding why the idea of inserting backwards in that way in the first stage of creating the final string is "correct". I could simulate it on some examples and see that it works, but can't reach to a firm decision like I did with the second phase of the solution when it prints and answers.

Can someone help me and provide more rigid argument for the correctness of the given solution ? (or other solution if possible)