D. Listen to the Music
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Yuki likes listening to music. She has $$$n$$$ favorite songs, numbered from $$$1$$$ to $$$n$$$.

She created two playlists, and each playlist contains each of these $$$n$$$ songs exactly once. In the first playlist, the $$$i$$$-th song is song $$$a_i$$$. In the second playlist, the $$$i$$$-th song is song $$$b_i$$$.

Whenever Yuki wants to listen to music, she chooses one of the two playlists and starts playing it from the first song. She may stop after any song finishes, but she will never stop in the middle of a song. In other words, each time she listens to music, she chooses one of the two playlists and listens to a non-empty prefix of it.

A year has passed, and Yuki's music system reports that song $$$i$$$ was listened to exactly $$$c_i$$$ times in total. However, Yuki suspects that this statistic may be incorrect. Please determine whether there exists some possible listening history such that, for every song $$$i$$$, the total number of times song $$$i$$$ was listened to is exactly $$$c_i$$$. Note that Yuki may not have listened to any music at all last year.

Input

The first line contains a positive integer $$$n$$$, the number of Yuki's favorite songs.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, representing the order of the songs in the first playlist.

The third line contains $$$n$$$ positive integers $$$b_1, b_2, \ldots, b_n$$$, representing the order of the songs in the second playlist.

The fourth line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$, where $$$c_i$$$ is the total number of times song $$$i$$$ was listened to.

  • $$$1 \leq n \leq 5000$$$
  • Both $$$a$$$ and $$$b$$$ are permutations of $$$1, 2, \ldots, n$$$.
  • $$$0 \leq c_i \leq 10^9$$$
Output

If there exists a possible listening history such that the number of times each song was listened to matches the reported statistics, output Yes. Otherwise, output No.

Examples
Input
5
2 4 1 3 5
3 1 2 5 4
3 3 2 3 0
Output
Yes
Input
3
1 2 3
2 1 3
0 0 1
Output
No
Note

Explanation for Sample 1

Consider the playlists $$$a = [2, 4, 1, 3, 5]$$$ and $$$b = [3, 1, 2, 5, 4]$$$. Suppose Yuki listens to four prefixes as follows:

  • The first $$$2$$$ songs of the first playlist, so songs $$$2$$$ and $$$4$$$ are listened to once.
  • The first $$$3$$$ songs of the first playlist, so songs $$$2, 4$$$ and $$$1$$$ are listened to once.
  • The first $$$4$$$ songs of the first playlist, so songs $$$2, 4, 1$$$ and $$$3$$$ are listened to once.
  • The first $$$2$$$ songs of the second playlist, so songs $$$3$$$ and $$$1$$$ are listened to once.

Then the total listening counts are exactly $$$[3, 3, 2, 3, 0]$$$, which matches the reported statistics. Hence, the answer is Yes.