#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[1000010];
int h[1000010];
int hh[1000010];
int l=1,r=0;
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(r>=l&&h[r]>a[i])r--;
        h[++r]=a[i];
        hh[r]=i;
        if(hh[l]+k<=i)l++;
        if(i>=k)cout<<h[l]<<" ";
    }
    cout<<"\n";
    l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        while(r>=l&&h[r]<a[i])r--;
        h[++r]=a[i];
        hh[r]=i;
        if(hh[l]+k<=i)l++;
        if(i>=k)cout<<h[l]<<" ";
    }
}   
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
    string a;
    string b;
    cin>>a>>b;
    int n=a.size();
    int m=b.size();
    vector<int>ne(m);
    for(int i=1,j=0;i<m;i++)//
    {
        while(j&&b[j]!=b[i])j=ne[j-1];
        if(b[i]==b[j])j++;
        ne[i]=j;
    }
    for(int i=0,j=0;i<n;i++)
    {
        while(j&&a[i]!=b[j])j=ne[j-1];
        if(a[i]==b[j])j++;
        if(j==m)
        {
            cout<<i-m+2<<"\n";
            j=ne[m-1];
        }
    }
    for(int i=0;i<m;i++)
        cout<<ne[i]<<" ";
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  int t;
//  cin>>t;
//  while(t--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    string a;
    string b;
    cin>>a>>b;
    int m=b.size();
    b+=" ";
    b+=a;
    int n=b.size();
    vector<int>z1(n);
    for(int i=1,l=0,r=0;i<n;i++)
    {
        if(z1[i-l]<r-i+1)
        {
            z1[i]=z1[i-l];
        }
        else
        {
            z1[i]=max(0,r-i+1);
            while(i+z1[i]<n&&b[z1[i]]==b[z1[i]+i])z1[i]++;
            l=i;
            r=i+z1[i]-1;
        }
    }
    z1[0]=m;
    long long ans1=0ll;
    long long ans2=0ll;
    for(int i=0;i<m;i++)
    {
        ans1^=1ll*(i+1ll)*(z1[i]+1ll);
    }
    for(int i=m+1;i<n;i++)
    {
        ans2^=1ll*(i-m)*(z1[i]+1ll);
    }
    cout<<ans1<<"\n"<<ans2<<"\n";

}
signed main() {
    cin.tie(0), cout.tie(0);
    // int t = 1;
    // cin >> t;
    // while (t--)
    solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
namespace trie
{
    int next[N][26],cnt;
    bool vis[N],exist[N];
    void init()
    {
        memset(next,0,sizeof(next));
        cnt=1;
    }
    void insert(const string &s)
    {
        int cur=1;
        for(auto c:s)
        {
            if(!next[cur][c-'a'])
                next[cur][c-'a']=++cnt;
            cur=next[cur][c-'a'];
        }
        exist[cur]=true;
    }
    int find(const string &s)
    {
        int cur=1;
        for(auto c:s)
        {
            if(!next[cur][c-'a'])
                return 0;
            cur=next[cur][c-'a'];
        }
        if(exist[cur])return 1;
        return 0;
    }
}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        if(c=='I')
        {
            string a;
            cin>>a;
            trie::insert(a);
        }
        else
        {
            string a;
            cin>>a;
            if(trie::find(a))
                cout<<1<<"\n";
            else
                cout<<0<<"\n";
        }
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  int t;
//  cin>>t;
//  while(t--)
    solve();
}

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    string yuan;
    cin>>yuan;
    int n=yuan.size();
    string a="~";
    for(int i=0;i<n;i++)
    {
        a+=yuan[i];
        a+="~";
    }
    n=a.size();
    vector<int>d(n);
    for(int i=0,l=0,r=-1;i<n;i++)
    {
        int j=l+r-i;
        int dj=j>=0?d[j]:0;
        d[i]=max(min(dj,j-l+1),0);
        if(j-dj<l)
        {
            while(i-d[i]>=0&&i+d[i]<n&&a[i-d[i]]==a[i+d[i]])d[i]++;
            l=i-d[i]+1;
            r=i+d[i]-1;
        }
    }
    int ans=0;
    for(int i=1;i<n;i+=2)
    {
        ans=max(ans,(d[i]-1)/2*2+1);
    }
    for(int i=0;i<n;i+=2)
    {
        ans=max(ans,(d[i]-1)/2*2);
    }
    cout<<ans<<"\n";


}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  int t;
//  cin>>t;
//  while(t--)
    solve();
}