AT_abc307_h [ABC307Ex] Marquee

[problemUrl]: https://atcoder.jp/contests/abc307/tasks/abc307_h 英大文字および英小文字からなる長さ $ L $ の文字列 $ S $ が幅 $ W $ の電光掲示板に表示されており、$ S $ が右から左へ $ 1 $ 文字分の幅ずつスクロールするように切り替わっています。 表示は、$ S $ の最後の文字が左端から消えると同時に $ S $ の最初の文字が右端から現れる、$ L+W-1 $ 周期での繰り返しとなっています。 例えば $ W=5 $、$ S= $ `ABC` のとき、電光掲示板の表示は - `ABC..` - `BC...` - `C....` - `....A` - `...AB` - `..ABC` - `.ABC.` の $ 7 $ つの状態を繰り返します。（`.` は文字が表示されていないことを表します） より厳密には、各 $ k=0,\ldots,L+W-2 $ に対して、表示が次のようになっている相異なる状態が定まります。 - $ x $ を $ L+W-1 $ で割ったあまりを $ f(x) $ と表す。電光掲示板の左から $ (i+1) $ 番目の位置には、$ f(i+k)\

入力は以下の形式で標準入力から与えられる。 > $ L $ $ W $ $ S $ $ P $

答えを出力せよ。

### 制約 - $ 1\ \leq\ L\ \leq\ W\ \leq\ 3\times\ 10^5 $ - $ L,W $ は整数である - $ S $ は英大文字および英小文字のみからなる長さ $ L $ の文字列である - $ P $ は英大文字, 英小文字, `.`, `_` のみからなる長さ $ W $ の文字列である ### Sample Explanation 1 電光掲示板の表示が `....A`, `...AB`, `..ABC` であるときの $ 3 $ 状態が該当します。