Colorful Drink

Interview

Time limit2sMemory limit512 MB

Summary

Given colored liquids with densities and a top-to-bottom list of requested color layers, decide whether one liquid per layer has strictly decreasing densities.

Level: Medium6 of 10
Topics: Greedy, Binary search, Array, Sorting
Solved: No attempts yet

Problem

The Jambo Amusement Garden (JAG) sells colorful drinks made of several layers of color. These colorful drinks are made by pouring colored liquids of different densities from the bottom up.

You have already prepared several colored liquids of various colors and densities. You now receive drink requests that specify the color layers. The colorful drink you serve must satisfy the following conditions.

A mixed colored liquid cannot be used as a layer. For example, you cannot create a new liquid with a new color by mixing two or more colored liquids of different colors, nor create a liquid with a density between two liquids of the same color by mixing them.
Only a colored liquid with strictly lower density can be placed above a denser colored liquid. That is, you can put a layer of a colored liquid with density $x$ directly above the layer of a colored liquid with density $y$ if $x < y$ holds.

Your task is to write a program that determines whether a given request can be fulfilled with the prepared colored liquids under the above conditions.

Input

The input consists of a single test case in the following format.

$N$
$C_1$ $D_1$
$\vdots$
$C_N$ $D_N$
$M$
$O_1$
$\vdots$
$O_M$

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ), the number of prepared colored liquids. The next $N$ lines contain $C_i$ and $D_i$ ( $1 \leq i \leq N$ ). $C_i$ is a string of lowercase alphabets and denotes the color of the $i$ -th prepared colored liquid. The length of $C_i$ is between 1 and 20 inclusive. $D_i$ is an integer and denotes the density of the $i$ -th prepared colored liquid. The value of $D_i$ is between 1 and $10^5$ inclusive. The $(N+2)$ -nd line contains an integer $M$ ( $1 \leq M \leq 10^5$ ), the number of color layers in the drink request. The next $M$ lines contain $O_i$ ( $1 \leq i \leq M$ ). $O_i$ is a string of lowercase alphabets and denotes the color of the $i$ -th layer from the top of the drink request. The length of $O_i$ is between 1 and 20 inclusive.

Output

If the requested colorful drink can be served using some of the prepared colored liquids, print Yes. Otherwise, print No.

Examples5

Example 1
Input
```
2
white 20
black 10
2
black
white
```
Expected output
```
Yes
```
Example 2
Input
```
2
white 10
black 10
2
black
white
```
Expected output
```
No
```
Example 3
Input
```
2
white 20
black 10
2
black
orange
```
Expected output
```
No
```

Example 4

Input

3
white 10
red 20
white 30
3
white
red
white

Expected output

Yes

Example 5

Input

4
red 3444
red 3018
red 3098
red 3319
4
red
red
red
red

Expected output

Yes