URI Online Judge | 2657

Sensate

By Abner Samuel P. Palmeira, IFSULDEMINAS BR Brazil

Timelimit: 1

Sensates, or Homo sensoriums, are a species of humans that are telepathically connected with other people throughout the world. A group of sensates is called a cluster, and the members of a cluster can contact each other regardless of where they are in the world. After knowing the organizers of programming contests were very worried because even if a person does not know how to program, if someone in your cluster knows, you will do well in the competition even without knowing anything. Because of this marathon organizers have created new rules for determining whether a person can participate in a competition or not.

Firstly, each person on the planet will receive a score of one to ten, in order to measure how well they program. After this for the person to participate she will have to fit into one of the categories below:

1. Do not be a sensate.

2. Be a sensible and have no one in the same cluster with programming level greater than five.

3. Be a sensible and have your programming level greater or equal to 5.

Develop a program that can determine whether or not a person can participate in programming competitions.

Input

The first line contains three integers N, M, and Q (1 ≤ N, M, Q ≤ 104) representing respectively the number of people, how many connections there are between these people and how many queries will be performed. Each of the following N lines contains a string S (1 ≤ |S| ≤ 10) and an integer V (0 ≤ V ≤ 10) representing respectively the person's name and its programming level. The next M will contain two strings S1 and S2 (1 ≤ |S1|, |S2| ≤ 10), representing that person S1 and S2 are in the same cluster. The next Q lines will contain a string T (1 ≤ |T| ≤ 10) that represents the name of the person who wants to participate in the competition.

Strings will be composed only of uppercase and lowercase letters.

Output

For each Q query print "S" if the person can compete or "N" otherwise.

Input Sample Output Sample

9 7 3

Capheus 1

Nomi 8

Lito 1

Will 1

Kala 1

Wolfgang 1

Sun 1

Riley 1

Abner 5

Capheus Nomi

Nomi Lito

Lito Will

Will Kala

Kala Wolfgang

Wolfgang Sun

Sun Riley

Lito

Nomi

Abner

N

S

S