G. Garbage In, Garbage Out
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

It is the 25th of July, 2525. Now that the usage of Large Language Models (LLMs) is so ubiquitous, it has become nearly impossible to find actual human-made articles on the internet and not get lost in all the gibberish produced by LLMs.

(Un)fortunately, LLM technology has regressed significantly. Neural networks have been trained on data that is mostly generated by older LLMs, which in turn were trained on even older recycled data. As a result, the output produced by most LLMs is a long string of lowercase letters, each chosen uniformly at random and independently of the others.

You decided to make a program to scavenge the internet in search of human-made articles. Your program must determine whether a given text is human-made or generated by an LLM.

A given text is guaranteed to be exactly one of the following:

  • Human-made, in which case it is a fixed concatenation (without spaces) of words from a given word list.
  • Not human-made and, therefore, generated by an LLM, in which case each character is chosen independently and uniformly at random.
Input

The input consists of:

  • One line with a string $$$s$$$, the given text to check.
  • One line with an integer $$$n$$$, the number of words in the word list.
  • $$$n$$$ lines, each with a string $$$w$$$ ($$$6 \leq |w| \leq 10$$$), the words in the word list. The words in the word list are distinct and fixed per test case.
All input strings only consist of English lowercase letters (a-z).

Your submission will be run on exactly $$$100$$$ test cases, all of which will have $$$|s| = 3\cdot10^5$$$ and $$$n = 5000$$$. The samples are smaller and for illustration only.

For each test case where $$$s$$$ is human-made, $$$s$$$ is fixed and does not change between each of your submissions. For each test case where $$$s$$$ is generated by an LLM, each of your submissions will receive a new string $$$s$$$, generated from independently and uniformly picking random English lowercase letters (a-z).

Output

If the given string was human-made, output "yes". Otherwise, if it was generated by an LLM, output "no".

Examples
Input
ballooncodingballoonacceptedchallengechallengecoding
5
accepted
balloon
challenge
coding
algorithms
Output
yes
Input
nlaiueakuyclocedxlwvxdbiifqjbinucjabzyaqakhohgympi
5
aaaaaaaaaa
bbbbbbbbbb
aababbb
aaabbbaaa
abaaba
Output
no
Input
aaaaaaaaaaabbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbbbbbbbb
5
aaaaaaaaa
bbbbbbbbbb
aabbbbb
aaaaabbbb
bbbbba
Output
yes