String Match and Swap

Background

Congcong is organizing a pile of strings. He wants to rearrange these strings according to a special rule to achieve a certain balance. This rule involves matching strings by their first characters and swapping positions, but once a string's position has been swapped, it can no longer participate in subsequent matches.

Problem Description

We'll say that 2 strings "match" if they are non-empty and their first chars are the same. Loop over and then return the given array of non-empty strings as follows: if a string matches an earlier string in the array, swap the 2 strings in the array. When a position in the array has been swapped, it no longer matches anything. Using a map, this can be solved making just one pass over the array. More difficult than it looks.

Input Format

Input is given from Standard Input in the following format.

s1 s2 s3 ... sn

Where s1, s2, ..., sn are non-empty strings, separated by spaces.

Output Format

Output is printed to Standard Output in the following format.

`["s'_1\