C. Beautiful Lyrics

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

You are given n words, each of which consists of lowercase alphabet letters. Each word contains at least one vowel. You are going to choose some of the given words and make as many beautiful lyrics as possible.

Each lyric consists of two lines. Each line consists of two words separated by whitespace.

A lyric is beautiful if and only if it satisfies all conditions below.

    • The number of vowels in the first word of the first line is the same as the number of vowels in the first word of the second line.
  • The number of vowels in the second word of the first line is the same as the number of vowels in the second word of the second line.
  • The last vowel of the first line is the same as the last vowel of the second line. Note that there may be consonants after the vowel.

Also, letters “a“, “e“, “o“, “i“, and “u” are vowels. Note that “y” is never vowel.

For example of a beautiful lyric,

hello hellooowww“”whatsup yowowowow
is a beautiful lyric because there are two vowels each in “hello” and “whatsup“, four vowels each in “hellooowww” and “yowowowow” (keep in mind that “y” is not a vowel), and the last vowel of each line is “o“.For example of a not beautiful lyric,

hey man“”iam mcdic
is not a beautiful lyric because “hey” and “iam” don’t have same number of vowels and the last vowels of two lines are different (“a” in the first and “i” in the second).How many beautiful lyrics can you write from given words? Note that you cannot use a word more times than it is given to you. For example, if a word is given three times, you can use it at most three times.

Input

The first line contains single integer n (1n10^5 1≤n≤10^5) — the number of words.

The i-th of the next n lines contains string si consisting lowercase alphabet letters — the i-th word. It is guaranteed that the sum of the total word length is equal or less than 106106. Each word contains at least one vowel.

Output

In the first line, print mm — the number of maximum possible beautiful lyrics.

In next 2m lines, print mm beautiful lyrics (two lines per lyric).

If there are multiple answers, print any.

Examples

Input

Output

Input

Output

Input

Output

Note

In the first example, those beautiful lyrics are one of the possible answers. Let’s look at the first lyric on the sample output of the first example. “about proud hooray round” forms a beautiful lyric because “about” and “hooray” have same number of vowels, “proud” and “round” have same number of vowels, and both lines have same last vowel. On the other hand, you cannot form any beautiful lyric with the word “codeforces“.

In the second example, you cannot form any beautiful lyric from given words.

In the third example, you can use the word “same” up to three times.





本题又是最讨厌的字符串大模拟
由于题目中说了每个单词都至少有一个元音字母
(Each word contains at least one vowel. )
于是开始分类
为了加速我在此处分类所用的vector定义了[100010][6]这么大
第一维代表元音数目
第二维代表结尾元音
然后按照优先级开始分类
由于所有单词都具有元音字母
并且要求是最末一个单词元音相同
所以先把这一部分的单词挑出来
优先作为第二个单词(称为优先级1)
剩下的元音相同的挑出来
优先级降低(称为优先级2)
然后按照一个优先级1一个优先级2的顺序排列
优先级2的排完了过后
每两个优先级为1的两两组合
最后再生成几组数据
能组成的组数的总数量就是

其中sp1是优先级为2的(也就是优先放在第一个的)

sp2自然是优先放在第二个的

(本题被查重了)
(枯辽)


 

2019-06-12  00:30:20  Author: WindCry1

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注