配点 : $300$ 点

問題文

すぬけくんは，$0$ と $1$ からなる長さ $N$ の整数列 $a=(a_1,a_2,\cdots,a_N)$ と，空の整数列 $b$ を持っています． $a$ の初期状態は入力で与えられ，$a_i=S_i$ です．

すぬけくんは，以下の $3$ 種類の操作を好きな順番で好きな回数行えます．

• $a$ を右シフトする．つまり，$a$ を $(a_N,a_1,a_2,\cdots,a_{N-1})$ で置き換える．
• $a$ を左シフトする．つまり，$a$ を $(a_2,a_3,\cdots,a_N,a_1)$ で置き換える．
• $b$ の末尾に現在の $a_1$ の値を追加する．

長さ $M$ の整数列 $T=(T_1,T_2,\cdots,T_M)$ が与えられます． $b$ を $T$ に一致させることができるか判定し，可能な場合は必要な操作回数の最小値を求めてください．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq S_i \leq 1$
• $0 \leq T_i \leq 1$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

$S_1$ $S_2$ $\cdots$ $S_N$

$T_1$ $T_2$ $\cdots$ $T_M$

出力

$b$ を $T$ に一致させることが不可能な場合，-1 を出力せよ． 可能な場合は，必要な操作回数の最小値を出力せよ．

3 4
0 0 1
0 1 1 0

6

以下のように $6$ 回操作すればよいです．

• $b$ の末尾に現在の $a_1$ の値を追加する．$b=(0)$ となる．
• $a$ を右シフトする．$a=(1,0,0)$ となる．
• $b$ の末尾に現在の $a_1$ の値を追加する．$b=(0,1)$ となる．
• $b$ の末尾に現在の $a_1$ の値を追加する．$b=(0,1,1)$ となる．
• $a$ を右シフトする．$a=(0,1,0)$ となる．
• $b$ の末尾に現在の $a_1$ の値を追加する．$b=(0,1,1,0)$ となる．

1 1
0
1

-1