Secret Santa P96432

A group of friends decides to play to the (regrettable) “Secret Santa”, in which each one makes, in principle anonymously, a present to other person of the group. You have obtained a list of who has made the present to who, together with the prices of the presents. With this information it is easy to know the balances of the friends. Write a program that computes and prints them.

Input

Input consists of a natural n followed by an empty line and n cases, separed by an empty line. Each case consists of a natural m≥ 2 that indicates the number of friends. Follow m lines, each one with the name of who has done the present, the name of the receiver, and the price of the present (a natural). The names consist of an uppercase letter followed by one or more lowercase letters. All the name of the same case are different.

Output

For each case, print m lines, each one with the name of a friend and his balance, in increasing order by balance. In the event of a tie, it must be written before the information conrresponding to the friend with the smallest alphabetically name. Print an empty line after each case.