2019 Africa Cup of Nations
Hamza Solutions Challenge

Players info and images credit @filgoal

Egypt @AFCON
Time limit per test: 1 second
Memory limit per test: 256 megabytes

Egypt national football team is getting ready to face Uganda next Sunday. Players are exerting much effort in the training to do their best in the following match. Coaches follow a weird strategy to choose the man of AFCON (Africa Cup of Nations). Let's call a player, whose total number of scored goals is a prime number, a PRIMO. The coaches will choose the highest PRIMO player to be the man of AFCON.

You are given N (the number of matches played) followed by N match description, Each description starts with M (the number of players who scored at the match) followed by M lines. Each line consists of the name of a player and S (the number of goals scored by the player), space-separated. Then you will be asked K queries. Each query(line) consists of the name of a player. For each query you have to calculate the minimum number of goals the player needs to score in the next match to be the man of the AFCON.

The players are busy training. We heard that you are a clever developer so we are challenging you to help the Egyptian players to know the minimum number of goals each player needs to score to be the man of AFCON.

Input

(1 ≤ N ≤ 100) — The number of matches played.

(1 ≤ M ≤ 23) — The number of players who scored at the match.

(1 ≤ S ≤ 10) — The number of goals scored by a player at the match.

(1 ≤ K ≤ 15) — The number of queries.

Output

The output should consist of K lines. Each line consists of the number of goals the player needs to score in the next match to be the man of AFCON.

Example

Input

3
2
Salah 2
Trezeguet 4
3
Elmohamady 3
AmrWarda 1
Hegazi 2
2
MarawanMohsen 1
Salah 3
3
Trezeguet
Salah
Elmohamady

Output

3
0
4

Explanation

We have 3 matches.

The 1st match Salah had 2 goals and Trezeguet had 4 goals.
The 2nd match Elmohamady had 3 goals, Amr Warda had 1 goal and Hegazi had 2 goals.
The 3rd match Marawan Mohsen had 1 goal, and Salah had 3 goals.

So the final scores are

Salah 5 goals Trezeguet 4 goals Elmohamady 3 goals
Amr Warda 1 goal Hegazi 2 goals Marawan Mohsen 1 goal

So far Salah is the highest PRIMO and needs no more goals to be the man of AFCON. But what about the other players ?

Trezeguet scored 4 goals

Needs 3 more goals to have 7 goals and exceed Salah
Salah scored 5 goals

Needs no more goals, He is the highest PRIMO

Elmohamady scored 3 goals

Needs 4 more goals to have 7 goals and exceed Salah

Problem Credits (Written and Tested by) @Kerolloz
Solutions Judged and Maintained @CodeCoursez
Made with @HamzaSolutions

Submit Your Solution

Hamza will contact the Winner

Programming Language
C++ (7.2.0)
Python 3.6
Java 7
Submit
Have any problem ?
Please let us know by opening an issue GitHub