Minimum Cyclic Shifts to Match Pattern

You are given a melody represented as a sequence of n integers and a pattern represented as a sequence of m integers. A cyclic shift is defined as removing the first element of the melody and appending it to its end.

Your task is to determine the minimum number of cyclic shifts required so that the melody begins with the given pattern. In other words, find the smallest non-negative integer s such that after performing s cyclic shifts, the first m numbers in the melody exactly match the pattern. If it is not possible to match the pattern with any amount of shifts, output -1.

This can be formally described with the following condition. Let the melody be represented as an array \(A = [a_0, a_1, \dots, a_{n-1}]\) and the pattern as \(P = [p_0, p_1, \dots, p_{m-1}]\). After s shifts, the condition to check is:

[ A_s[i] = a_{(s+i) \mod n} = p_i, \quad \text{for all } i = 0, 1, \dots, m-1. ]

If such an s exists, output the minimum s. Otherwise, output -1.

inputFormat

The input is given via STDIN in the following format:

The first line contains two space-separated integers n and m, where n is the length of the melody and m is the length of the pattern.

The second line contains n space-separated integers representing the melody.

The third line contains m space-separated integers representing the pattern.

outputFormat

Output a single integer via STDOUT: the minimum number of cyclic shifts required so that the melody starts with the pattern, or -1 if it is not possible.## sample

6 3
1 2 3 4 5 6
4 5 6

3