eolymp
Competitions

2019 Fall KBTU OPEN

Abusing 1Fit limits

1Fit - is a subscription-based startup, within 1Fit you can visit multiple gyms without buying separate subscriptions.

In 1Fit we have n fitnesses, m trainings and k sport types. All entities numbered consecutively starting from 1. Each training has fitnessID and sporttypeID specified.

There are r rules, each rule describes the book limit per user. In each rule specified fitness, list of sport types and limit, limit = -1 stands for an unlimited book, e.g. if fitnessID = 3 and sporttypes = [1, 2, 6] and limit = 7 means that the number of books with 3rd fitness and sporttype equals to 1 or 2 or 6 cannot exceed 7. One training cannot be booked multiple times. It's guaranteed that each pair fitnessID and sporttypeID can appear in at most one rule as well.

Aisultan recently bought a 1Fit subscription to get more healthy. He sent q consecutive book queries. For each query server must return either 'yes' or 'no', is training booked successfully or the booking was incorrect. Write a program to process all Aisultan's queries.

Input

The first line given three positive integer numbers n, m and k (1n, m, k100) - the number of fitnesses, trainings and sport types, respectively. Each of the next m lines contains two integers fitnessID, sporttypeID (1fitnessIDn, 1sporttypeIDk) - description of trainings: fitness ID and sport type ID of training. Next line contains one positive integer r (1r100) - number of rules. Each of the next r lines contains the first ID of fitness, following by the number of sport types in this rule and list of sport type ids and limit at the end. The next line contains one positive number q (1q100) - the number of Aisultan's queries. Each of the next q lines contains one integer - description of query: ID of training.

Output

For each query output either 'yes' or 'no'.

Note

In the example, we have 3 fitnesses, 8 trainings and 3 sport types. Training lists are: (1, 1), (1, 2), ..., i.e. training number 1 in fitness with ID 1 with sport type ID 1, training number 2 in fitness with ID 1 with sport type ID 2, ...

Have 4 rules:

  1. fitnessID = 1, sporttypeIDs = [2] limit = -1 - Aisultan can book trainings with fitnessID = 1 and sporttypeID = 2 unlimited times;

  2. fitnessID = 2, sporttypeIDs = [2, 3] limit = 2 - Aisultan can book trainings with fitnessID = 2 and sporttypeID = 2 or fitnessID = 2 and sporttypeID = 3 no more than twice in total;

  3. fitnessID = 3, sporttypeIDs = [1] limit = -1 - Aisultan can book trainings with fitnessID = 3 and sporttypeID = 1;

  4. fitnessID = 1, sporttypeIDs = [1] limit = 1 - Aisultan can book trainings with fitnessID = 1 and sporttypeID = 1 no more than once;

The first three queries Aisultan can book successfully. 4-th query will be 'no' because Aisultan cannot book 2nd training twice. Also 7th query's response is 'no', because Aisultan cannot book training with fitnessID = 1 and sporttypeID = 1 twice.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 8 3
1 1
1 2
2 2
2 3
3 1
3 3
3 1
1 1
4
1 1 2 -1
2 2 2 3 2
3 1 1 -1
1 1 1 1
9
1
2
3
2
4
5
8
6
7
Output example #1
yes
yes
yes
no
yes
yes
no
no
yes
Source 2019 Fall KBTU OPEN, Problem L