Practice on Toph

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

Eet Izz Phet!

Limits: 15s, 32 MB

A long long time ago, I left the country that was my home and with my head full of brains and shoes full of feet I went on a journey through the long lonely shores, snoring sleepy mountains and lush green forests. Then I got completely lost.

On my path, I met a philosopher who was lost too but he seemed very content. I said, “How?”. He told me, “Eet izz phet!”. I said, “What?”. With his husky voice, he told me it was my fate to get lost and greatness is not in merely accepting the fate but in loving it. Which seemed like… philosophy.

We became good friends and one day I told him I was a programmer. The philosopher laughed, “Ho ho ho! I noo a good poggamming poblom”. Then he told me, he’ll give me a list of words and a bunch of queries. Each query will ask whether a particular word was in the list he gave me. I said, “Huh, that’s easy. I need to keep a set.” Then the philosopher laughed again and told me the only computer we have right now has 32 MB memory but the list is 50 MB and it’s in the hard disk.

I cried, “Oh philosopher! The problem is too big for me. I can’t even fit it in my memory!”. Philosopher nodded with a serious face and asked me if I thought Hercules could still become Hercules if he didn’t face Hydra and beasts way bigger than himself?

Now, it is your fate to be your own Hercules and face the same problem.

Input

The test case will start with an integer N (1 ≤ N ≤ 100000), then N words will follow with one word in each line - this is the list. After that there will be another integer M (1 ≤ M ≤ 100000) and then M queries will follow with one word in each line. Each word will be at most 1000 ASCII lowercase alphabets (‘a’ - ‘z’). You can assume the entire input file will be at most 50 MB.

Output

For each query, print one line with the word “yes”, or “no” depending on whether that word was on the list or not.

Samples

InputOutput
5
nietzsche
socrates
epictetus
seneca
plato
2
epictetus
neruda
yes
no

Because the way Java handles memory, it’s pretty hard to solve this problem with Java. Even you have figured out the solution to reduce memory usage, you’ll have to use BufferedReader.read with InputStreamReader, read one by one character, stick to primitive types as much as you can, reuse your variables and call System.gc() after reading every 2000 words. Also note, the dataset was prepared with Linux, so newline is ‘\0’, which is a 10 if you’re reading with BufferedReader.read(). I wish Java handled memory differently, but it is fate.

Authors
Discussion