Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Candidate Consonant

By jamilasad · Limits 1s, 512 MB

Alice and Bob are playing with string. Alice gives Bob a string S with the following information: - S has length L consists of only lower case letters. - S contains at least one consonant and one vowel i.e. its minimum length can be 2. - In S, no vowels can be surrounded by a different vowel i.e. S can be “abaaac” but S cannot be “abaepl” as “a” and “e” are two different vowels.

Now Alice challenges Bob to find out the Candidate Consonants for each of the vowels in S based on the following rules:

  1. If there is a vowel and a set of consonants for it, then the Candidate Consonant of the vowel will be the lexicographically nearest consonant of that vowel. For example, if there is vowel “a” and some consonants “c”, “d” and “f”, then “c” is lexicographically nearest to “a” and hence it is the Candidate Consonant for “a” among “c”, ”d” and “f”. Again, if there is the vowel “e” and some consonants “c”, “d” and “f”, then “d” and “f” both are lexicographically nearest to “e” and in this situation lexicographically smaller one i.e. “d” (for this case) will be the Candidate Consonant for “e”.

  2. If S[i] is a vowel where (0 <= i <= L-1) then Bob has to look at both sides of S[i] until it passes over some consonants and reaches another vowel on both of its sides. Its Candidate Consonant will be from among the consonants it passed over. Example: Suppose S = “cebcatdcid” and we are looking for the candidate consonant for “a” at position 4 (string starting from position 0). Both “bc” on a’s left side and “tdc” on a’s right side has to be taken into consideration as the previous character of “bc” is a vowel and so is the next character of “tdc”. Then the Candidate Consonant of “a” will be from “b”, ”c”, ”t”, ”d”, ”c” and that is “b”.

  3. If there is a case where a vowel has no vowel to its one or both of its sides, then all the consonants of those sides will be taken into consideration for finding out its Candidate Consonant. Example: Suppose S = “ccdeghup”. Candidate Consonant for “e” will be one from “ccd” and “gh”. In this case, the Candidate Consonant is “d”.

  4. If there are more than one vowel together than only the vowel which we are searching the Candidate Consonant for will be taken into consideration and other vowels will be skipped. And we will search for only its Candidate Consonant. Example: Suppose S = “cebcaatdcid” and we are looking for the candidate consonant for first “a” (at position 4) in “aa”. Then we will skip the second “a” (at position 5) and Candidate Consonant for first a will be searched from “bc” on their left and “tdc” on their right. In this case both “a”’s at position 4 and 5 has Candidate Consonant “b”.

Now Bob is at a loss and he wants you to find out the Candidate Consonants for all of the vowels in the string Alice has given to him.

Input

There is only a string S of length at most 50 characters in a single line.

Output

For each vowels in S print a single line containing P and C. Here, P is the position of the vowel in the string (position starts from 0) and C is its Candidate Consonant.

Samples

InputOutput
ccdeghup
3 d
6 p
InputOutput
abcnpo
0 b
5 n
InputOutput
cebcaatdcid
1 c
4 b
5 b
9 d


Discussion
Submit

Login to submit