Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

East(West)er Eggs

By RHaque · Limits 1s, 512 MB

It is time for the annual East(West)er Egg festival, where children across the country decorate their houses with painted eggs. For some unknown reason, they like to write numbers on the eggs they paint. Edward Elric painted nn eggs, and wrote a number from 11 to kk on each of them. After painting them, he arranged the eggs in a line and left them in his room for the paint to dry.

After coming back, Edward discovered that someone touched his eggs, and although there are still nn eggs in a line, they are no longer in the same order as they were when he left them. He remembers the original order of the numbers written on the eggs. Now that the eggs have been reordered, he wants to know if all the eggs he painted still remain, or if one or more of them have surely been replaced with other ones.

Input

The input consists of three lines. The first line contains nn and kk, as described above.

The second line contains nn space-separated integers, each within the range [1,k][1, k ], denoting the numbers written on the eggs in the order in which Edward left them in.

The third line contains nn space-separated integers, each within the range [1,k][1, k], denoting the numbers written on the eggs in the order in which Edward found them.

Constraints

1n,k1051 \leq n, k \leq 10^5

Output

If one or more of Edward’s eggs were surely replaced, output “YES” (without the quotes). Otherwise, output “NO”, (without the quotes). Check the sample I/O for clarifications.

Samples

InputOutput
5 5
1 2 4 2 5
2 3 1 4 5
YES

There was no egg numbered 3 among Edward’s eggs. Since there is an egg numbered 3 now, at least one of these eggs must have been replaced.

InputOutput
5 5
1 2 4 2 5
2 2 2 4 5
YES

In the original sequence, there were two eggs numbered 2. After Edward came back, he found three eggs numbered 2. Furthermore, Edward had one egg numbered 1, which he did not find after coming back. That means that at least one of the eggs were surely replaced.

InputOutput
5 5
3 2 2 3 3
3 2 3 2 3
NO

Edward had 2 eggs coloured 2, and 3 eggs coloured 3 originally. After he came back, there were still 2 eggs coloured 2, and 3 eggs coloured 3. This shows that although the eggs have surely been rearranged, there is a possibility that all the eggs we find here are all Edward’s eggs. Since we cannot confirm that one or more eggs were replaced, we output “NO”.


Input file can be very large, use faster I/O methods.

    Discussion

    Statistics


    78% Solution Ratio

    TanbeerEarliest, 2w ago

    user.804932Fastest, 0.0s

    ShajibewucseLightest, 262 kB

    mdvirusShortest, 424B

    Submit

    Login to submit