Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3298

Time Limit: 5 Seconds      Memory Limit: 32768 KB

A company has developed a new digital lock. It looks like a round plate, and has N buttons evenly distributed at the edge of the plate. In order to unlock it, you must first choose a button and type the correct number, and then choose the next button which must be adjacent and in clockwise direction. You can unlock it only if you typed all the buttons correctly.

Peter, known as a famous hacker, wants to write a program to hack this kind of lock. So he bought lots of these locks. After several days' analyzing, Peter is now able to write a program to generate a number sequence which probably can unlock the lock. First he chooses one number in the sequence to start, then choose one button of the lock. If it matches, he can go to next button and next number which is adjacent and in forward direction. But if it doesn't match, the sequence will fail and cannot be used again.

Now Peter wants to test the sequence. If a sequence can successfully unlock the lock, it will be marked as good, otherwise the sequence is bad. What's more, if the sequence is good, Peter wants to know the max number of buttons the sequence can match. In other words, Peter will continue to match the buttons even if the lock has been unlocked.


There are multiple cases (no more than 50).

The first line of each case is two integers: the number of the buttons N and the number of the sequence M (1 <= N <= 1000, 1 <= M <= 1000000).

Then two lines followed. The first line is the N numbers which the buttons needed. The second line is the number sequence. All the number will be in [-2^31, 2^31 - 1].


For each case, if the sequence is bad, just output "bad". Otherwise, output the max number of buttons the sequence can match.

Sample Input

3 5
2 3 1
2 1 3 5 4
3 8
1 3 2
2 3 2 1 3 2 1 5

Sample Output



In the second sample, you can choose the second number of the sequence and the second button. Now you can match 6 buttons: 3 2 1 3 2 1

Author: YANG, Kete
Source: ZOJ Monthly, February 2010
Submit    Status