K. Keep the Fairness
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ teams and $$$m$$$ distinct souvenirs. The teams are numbered from $$$1$$$ to $$$n$$$, and the souvenirs are numbered from $$$1$$$ to $$$m$$$.

Each team ranks all souvenirs from most preferred to least preferred. The ranking of team $$$i$$$ is a permutation [ t_{i,1},t_{i,2},...,t_{i,m}, ] where $$$t_{i,1}$$$ is its most preferred souvenir.

Every souvenir has already been assigned to exactly one team. Let $$$a_k$$$ be the team to which souvenir $$$k$$$ is assigned. A team may receive any number of souvenirs, including none.

The assignment is called prefix-fair if the following condition holds:

  • For every team $$$i$$$, every other team $$$j$$$, and every integer $$$L$$$ with $$$1\le L\le m$$$, among the first $$$L$$$ souvenirs in team $$$i$$$'s ranking, the number assigned to team $$$i$$$ is at least the number assigned to team $$$j$$$.

Both numbers in this comparison are counted using team $$$i$$$'s ranking. Equality is allowed.

Determine whether the given assignment is prefix-fair.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 2000$$$), the number of teams and the number of souvenirs.

The next $$$n$$$ lines describe the rankings. The $$$i$$$-th of these lines contains $$$m$$$ pairwise distinct integers $$$t_{i,1},t_{i,2},\dots,t_{i,m}$$$ ($$$1\le t_{i,k}\le m$$$), from team $$$i$$$'s most preferred souvenir to its least preferred souvenir. Thus, each line is a permutation of $$$1,2,\dots,m$$$.

The last line contains $$$m$$$ integers $$$a_1,a_2,\dots,a_m$$$ ($$$1\le a_k\le n$$$), where $$$a_k$$$ is the team to which souvenir $$$k$$$ is assigned.

Output

Print one line containing YES if the assignment is prefix-fair. Otherwise, print NO.

The answer is case-sensitive.

Examples
Input
3 6
1 2 3 4 5 6
2 1 3 5 4 6
3 1 2 6 4 5
1 2 3 1 2 3
Output
YES
Input
2 4
1 2 4 3
2 1 4 3
1 2 1 2
Output
NO
Note

In the first example, consider team $$$2$$$. The owners of the souvenirs in its ranking are [ 2,1,3,2,1,3. ] In every prefix, team $$$2$$$ occurs at least as many times as each of team $$$1$$$ and team $$$3$$$. The same property holds for teams $$$1$$$ and $$$3$$$, so the assignment is prefix-fair.

In the second example, the first three souvenirs in team $$$1$$$'s ranking are $$$1,2,4$$$. Team $$$1$$$ receives only souvenir $$$1$$$, while team $$$2$$$ receives souvenirs $$$2$$$ and $$$4$$$. Therefore, this prefix contains one souvenir assigned to team $$$1$$$ and two assigned to team $$$2$$$, so the assignment is not prefix-fair. Notice that both teams still receive two souvenirs in total; equal total numbers alone are not sufficient.