【算法】利用有限自动机进行字符串匹配

【算法】利用有限自动机进行字符串匹配2012-03-08 博客园银河Timus 1102. Strange Dialog 要求判断给定的输入是否为合法的对话。

1102. Strange Dialog

Time Limit: 1.0 second

Memory Limit: 16 MB

One entity named "one" tells with his friend "puton" and their conversation is interesting. "One" can say words "out" and "output", besides he calls his friend by name. "Puton" can say words "in", "input" and "one". They understand each other perfect and even write dialogue in strings without spaces.

You have N strings. Find which of them are dialogues.

Input

In the first line of input there is one non-negative integer N ≤ 1000. Next N lines contain non-empty strings. Each string consists of small Latin letters. Total length of all strings is no more then 10⁷ characters.

Output

Output consists of N lines. Line contains word "YES", if string is some dialogue of "one" and "puton", otherwise "NO".

Sample

input	output
6puton inonputin oneputonininputoutoutput oneininputwooutoutput outpu utput	YESNO YES NO NO NO

input

output

6puton

inonputin

oneputonininputoutoutput

oneininputwooutoutput

outpu

utput

YESNO

YES

Problem Author: Katya Ovechkina

Problem Source: Tetrahedron Team Contest May 2001