```cpp

include <bits/stdc++.h>

using namespace std;

define il inline

define N 1000100

define Inf 0x3f3f3f3f

int Kmp[N]; char Mode[N], S[N]; i