2024 Africa Cup of Nations
AFCON Challenge

Players info and images credit @filgoal.

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

The Egyptian national football team is getting ready to face Ghana this evening. The players are putting in significant effort during training to deliver their best performance in the upcoming match. Coaches have a unique way of picking the best player a.k.a "man of AFCON" (Africa Cup of Nations). A player is considered a "PRIMO" if the total number of goals they've scored is a prime number. The coaches will choose the highest PRIMO player as the man of AFCON.

You are given N, the number of matches played so far, followed by N match description.
Each match description starts with M, the number of players who scored at the match, followed by M lines.
Each line consists of a string P, the player name, and G, the number of goals scored by that player at this match.
Then you will be asked K queries. Each query (line) consists of a player name. 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 with their training, and we've heard you're a clever developer. Can you help the Egyptian players know how many goals they need to score to become the man of AFCON?

Input

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

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

(1 ≤ length(S) ≤ 100) — The name of the player. The name consists of uppercase and lowercase English letters only. (No spaces in the name)

(1 ≤ G ≤ 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
AliGabr 3
OmarMarmosh 1
Hegazi 2
2
Elneny 1
Salah 3
3
Trezeguet
Salah
AliGabr

Output

3
0
4

Explanation

We have 3 matches.

The 1st match Salah scored 2 goals and Trezeguet scored 4 goals.
The 2nd match Ali Gabr scored 3 goals, Omar Marmosh scored 1 goal and Hegazi scored 2 goals.
The 3rd match Elneny scored 1 goal, and Salah scored 3 goals.

So the final scores are

Salah 5 goals Trezeguet 4 goals Ali Gabr 3 goals
Omar Marmosh 1 goal Hegazi 2 goals Elneny 1 goal

So far, Salah is the highest PRIMO and needs no more goals to be the man of AFCON. But what about 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

Ali Gabr scored 3 goals

Needs 4 more goals to have 7 goals and exceed Salah

Made with @Kerollos Magdy
UI was originally developed by Amr Salama for the 2019 AFCON challenge

Submit Your Solution

The winners will be announced next Sunday

Programming Language
Submit
Facing any issues?
Please let us know by opening an issue GitHub