Little Stars (2 Points)

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Little Stars

Twinkle, twinkle, little star,

How I wonder what you are!

Up above the world so high,

Like a diamond in the sky.

When the blazing sun is gone,

When he nothing shines upon,

Then you show your little light,

Twinkle, twinkle, all the night.

The end your nature does foretell

No more humans it does spell

When stars align and planets curve

All we may do is observe

You have been watching the night sky for many years, and have a log of the major event that occurred every day. For example:

  • 14/08, I saw two shooting stars
  • 15/08, Venus was visible to the naked eye
  • 16/08, There was a full moon tonight

You now have a vast collection of records, and have recently been told of a great cataclysm that will certainly occur when a certain combination of events happen, one day after the other:

  • On the first day, three shooting stars will be visible in the night sky
  • For the next 3 days, three planets will be visible to the naked eye
  • On the next day, the brightest star in the sky will be temporarily occluded by the moon
  • Then, the world will end.

All prophesized events will only occur once, or in a contiguous group of days. For example, it is impossible to prophesise a single shooting star, then 3 days of planets being visible, then another single shooting star day.

You'd like to know at any point in your log, the furthest along this sequence of these events we have ever ventured, with no gaps.

Because you see these events so often, you've categorised them into easy to write but hard to remember hexadecimal strings.

So, your log for the week might be:

A4B FF3 B21 CD9 8D0 05C ABD

And the prophesized events might be:

CD9 8D0 A4B FF3 B21 33C 000

The longest sequence of events that actually occurred this week is CD9 8D0. It is not A4B FF3 CD9 - we need to start at the beginning of the sequence of cataclysm events.

Input

Input will contain 2 space separated integers, n and m. These are the lengths of your log, and the log of cataclysm events

2 lines will follow, each containing space-separated strings representing events. The first line will contain n strings, representing your log, and the second will take m strings, representing the cataclysm events

Output

Output a single integer, representing the furthest along the cataclysm events you've ever recorded.

Constraints

  • 1 \leq n, m \leq 2 \times 10^5
  • Each string will contain at most 6 characters

Example 1

For input

7 7
A4B FF3 B21 CD9 8D0 05C ABD
CD9 8D0 A4B FF3 B21 33C 000

The correct output is

2

Since the furthers we get along the cataclysm is CD9 8D0.

Example 2

For input

11 6
A B C A A B B C C C D
A B B C C D

The correct output is

5

Since the furthers we get along the cataclysm is A B B C C.


Comments

There are no comments at the moment.