Problem Description

Hashing involves converting a complex data structure (such as strings or arrays) into integers for easier reference and manipulation.

However, although hashing speeds up performance, it is at the expense of accuracy as 2 different objects might be hashed into the same integer.

For this case, you are supposed to design a program that checks a given list of strings and hash them into an integer using the below hashing algorithm. Subsequently, you are supposed to sort those strings based on the value of their hash (integer that is produced from the hashing algorithm). In the event that there are 2 strings with the same hash, the alphabetically smaller string should be ordered first.

Hashing Algorithm

For this problem, the hash would be the bitwise-xor product of each character of the string (in ASCII representation).

The string ' abc ' will have a hash of a ^ b ^ c (where ^ denotes the bitwise-xor function). Bitwise-xor is commutative, so a ^ (b ^ c) is equivalent to (a ^ b) ^ c. The numerical hash value of the string ' abc ' is 96 (97 ^ 98 ^ 99)

To utilize bitwise-xor, you can use the operator

for C and C++ programmers.

a = 6 ^ 2;
will result in
having the result of the bitwise-xor of 6 and 2.

More specifically, the following code illustrates how you can hash a STL String

string str = "abcdefg";
int hash = 0;
for (int i = 0; i < str.length(); i++) {
	hash = hash ^ str[i];

The hash of the string, str, will be stored in the integer, hash.


The first line of input will consist of 1 integer, N. N denotes the number of strings in the list. N will be a positive integer not exceeding 10000.

The following N lines will consist of a string each. It is guaranteed that the string will contain no spaces and will not exceed 1000 characters long.


N lines are expected in your output. Each of these lines should consist of only 1 string each.

You are tasked to output those N strings in sorted order, with the string with the smallest hash first. If 2 strings have the same hash, the alphabetically smallest string should be printed first. (STL '<' function)


For this question, you are supposed to input from '' and output to 'hasher.out'.

Sample Input


Sample Output


Explanation of Sample Output

abc, acb, cab, bac both have the same hash value of 96. bad has a hash value of 103. As such, bad is ordered after those 4 strings. Since those 4 strings have the same hash value, they are printed in alphabetical order.