DMOPC '21 Contest 10 P1 - Japaneasy

View as PDF

Submit solution


Points: 5
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Edward spends a lot of time learning Japanese in hopes that he can one day actually read his collection of raw light novels. However, Japanese is a hard language. To give himself a confidence boost, he decided to invent a new language called Japaneasy and master that instead.

In short, Japaneasy consists of the following 30 characters with their respective sounds listed below:

knhmr
あ aか kaな naは haま maら ra
い iき kiに niひ hiみ miり ri
う uく kuぬ nufuむ muる ru
え eけ keね neへ heめ meれ re
お oこ koの noほ hoも moろ ro

In particular, note the irregularity of ふ.

He also defines a valid Japaneasy word as a word whose sounds are a sequence of the given sounds. Formally speaking, a string is valid if it can be constructed by continually appending one of the 30 strings (Japaneasy characters) given above to an empty string.

To learn the language efficiently, Edward decides that he needs an app that can check whether T given strings S_1, \dots, S_T are valid Japaneasy. Please help him make it.

Constraints

1 \le T \le 10^6

Each string contains only lowercase characters.

The sum of the lengths of all strings does not exceed 10^6.

Input Specification

The first line contains a number T, the number of strings.

The next T lines each contain one string S_i, the word to be evaluated.

Output Specification

Output T lines, the i^\text{th} line containing YES if S_i is a valid Japaneasy word or NO otherwise.

Sample Input

8
hairu
hairimashita
hu
kakakakakaka
akakakakakak
hiragana
hirakana
asunabestgirl

Sample Output

YES
NO
NO
YES
NO
NO
YES
NO

Explanation

For the first string, hairu is valid Japaneasy since it consists of the Japaneasy characters ha, i, and ru.

For the second string, it is impossible to make the substring shi with Japaneasy characters.

For the third string, note that hu is not a Japaneasy character.


Comments

There are no comments at the moment.