Jermichael runs a mannequin store, where he specialises in making all types of mannequin body parts.

He sells these components to small fashion designers and clothing stores. Recently he even sold 100 mannequins to his local McDonald's for their 100-year anniversary, allowing them to make an army of Ronald McDonalds.

Jermichael has noticed that his store is in a bit of a pigsty after he had to ship 100 mannequins to McDonald's. A shelf of mannequin heads are facing in many different directions.

The direction of a head on the shelf is determined by its name tag.

• A mannequin head is facing leftward if its name contains an odd number of vowels.
• A mannequin head is facing rightward if its name contain an even number of vowels.

Jermichael wishes to change the orientation of some of the heads on the shelf, so they all face in one direction. Can you give him a list of the name tags, which reflect all the heads facing in the same direction?

A head that is initially facing leftwards on the shelf could be represented by the name string abc, which contains an odd number of vowels. After rotation to face rightwards, its name would read cba.

Input

The first line contains a single integer ~n~, the number of mannequin heads on the shelf.

The next line contains ~n~ space-separated strings ~s_1\ \dots\ s_n~ (~1 \leq length(s_i) \leq 100~), the label name of each of the mannequin heads. Each name consists of only lower case english letters and spaces. The sum of lengths has ~\sum_i length(s_i) \leq 10^5~.

Output

Output every mannequin head name as it appears on the shelf after aligning all mannequin heads to match the orientation of the first head.

The first head is identified as the first name in the input string.

Output each name on a new line.

Example

Input 1

4
jamie marcus jim lebron

Output 1

jamie
sucram
jim
norbel

jamie contains three vowels, and hence, faces leftward. jamie is the first mannequin head on the shelf, and is therefore the desired direction for all other mannequin heads.

• marcus contains 2 vowels (facing right), so require a flip.
• jim contains 1 vowels (facing left), so can remain as is.
• lebron contains 2 vowels (facing right), so require a flip.

Input 2

3
barbeque bacon burger

Output 2

barbeque
bacon
burger

All names have an even number of vowels, and hence, all are facing the same direction (right).

Input 3

1
f

Output 3

f