A conference check-in system keeps two records. The first is the attendee roster: every registrant's internal id and display name, listed in the order each person registered. The second is the badge-printing log: for every attendee whose physical badge has already been printed, one line records their internal id together with the badge number engraved on it. Not every attendee has been printed yet, and the log never contains more than one printed-badge line for the same attendee id. For each attendee on the roster, in registration order, report their display name followed by their badge number — or -1 if no badge has been printed for them yet.

Input format

• Line 1: a single integer n (1 <= n <= 100000) — the number of attendees on the roster.
• Next n lines: id name, where id is a distinct integer (1 <= id <= 10^9) and name is a non-empty string of at most 20 characters containing no whitespace.
• Next line: a single integer m (0 <= m <= n) — the number of printed-badge log entries.
• Next m lines: id badgeNumber, where id matches exactly one of the attendee ids listed above, no id appears in more than one log line, and badgeNumber is a positive integer (1 <= badgeNumber <= 10^9).

Output format

Print exactly n lines. The i-th line must contain the name of the i-th roster attendee (in the order they appear in the input) followed by a single space and their badge number, or -1 if that attendee has no entry in the printed-badge log.

Constraints

• All n roster ids are pairwise distinct.
• Every log-entry id is guaranteed to belong to some attendee on the roster.

3
101 Ava
102 Ben
103 Cy
2
102 55
101 30

Ava 30
Ben 55
Cy -1

2
5 Uma
9 Zoe
0

Uma -1
Zoe -1