#include<bits/stdc++.h>

 using namespace std;

 #define maxn 1000005

 struct node{int id,val;};

 int n,m,k,l,a,b,c,mx[maxn],ma[maxn];

 deque<node>q1;deque<node>q2;

 int main(){cin>>n>>m;

     for(int i=;i<=n;i++){cin>>a;

         while(!q1.empty()&&q1.back().id<i-m+)q1.pop_back();

         while(!q2.empty()&&q2.back().id<i-m+)q2.pop_back();

         while(!q1.empty()&&q1.front().val<a)q1.pop_front();

         q1.push_front({i,a});

         while(!q2.empty()&&q2.front().val>a)q2.pop_front();

         q2.push_front({i,a});

         if(i>=k)mx[i]=q1.back().val,ma[i]=q2.back().val;

     }for(int i=m;i<=n;i++)cout<<ma[i]<<" ";cout<<endl;

      for(int i=m;i<=n;i++)cout<<mx[i]<<" ";

 } 

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define maxn 100005

 ll n,m,k,l,a,b,c,d,tree[maxn*],lazy[maxn*],s[maxn];

 #define lson (node<<1)

 #define rson (lson|1)

 void build(int node,int l,int r){

     if(l==r){tree[node]=s[l];return ;}int mid=(l+r)>>;

     build(lson,l,mid);build(rson,mid+,r);tree[node]=tree[lson]+tree[rson];

 }

 void pushup(int node,int l,int r){if(lazy[node]==){return ;}

     int mid=(l+r)>>;

     tree[lson]+=lazy[node]*(mid-l+);tree[rson]+=lazy[node]*(r-mid);

     lazy[lson]+=lazy[node],lazy[rson]+=lazy[node];lazy[node]=;

 }

 void add(int node,int l,int r,int x,int y,int k){

     if(l==x&&y==r){tree[node]+=k*(r-l+);lazy[node]+=k;return ;}

     int mid=(l+r)>>;pushup(node,l,r);

     if(y<=mid)add(lson,l,mid,x,y,k);else if(x>=mid+)add(rson,mid+,r,x,y,k);

     else add(lson,l,mid,x,mid,k),add(rson,mid+,r,mid+,y,k);

     tree[node]=tree[lson]+tree[rson];

 }

 ll query(int node,int l,int r,int x,int y){

     if(l==x&&y==r){return tree[node];}

     int mid=(l+r)>>;pushup(node,l,r);

     if(y<=mid)return query(lson,l,mid,x,y);else if(x>=mid+)return query(rson,mid+,r,x,y);

     else return query(lson,l,mid,x,mid)+query(rson,mid+,r,mid+,y);

 }

 int main(){

     cin>>n>>m;for(int i=;i<=n;i++)cin>>s[i];build(,,n);

     for(int i=;i<=m;i++){

         cin>>a;if(a==){

             cin>>a>>b>>c;add(,,n,a,b,c);

         }else{

             cin>>a>>b;cout<<query(,,n,a,b)<<endl;

         }

     }

 }

 #include<iostream>

 #include<cstdio>

 #define ll long long

 #define lson (node<<1)

 #define rson ((node<<1)+1)

 using namespace std;

 const int maxn=;

 int n,m;

 ll tree[maxn*],lazy_product[maxn*];

 ll lazy_sum[maxn*];

 ll s[maxn],p;

 void build(int node,int l,int r){lazy_product[node]=;

     if(l==r){tree[node]=s[l];return;}

     int mid=(l+r)>>;

     build(lson,l,mid);build(rson,mid+,r);

     tree[node]=tree[lson]+tree[rson];

 }

 void pushdown(int node,int l,int r,int mid){

     tree[lson]*=lazy_product[node];tree[rson]*=lazy_product[node];

     tree[lson]+=(mid-l+)*lazy_sum[node];tree[rson]+=(r-mid)*lazy_sum[node];

     tree[lson]%=p;tree[rson]%=p;

     lazy_product[lson]*=lazy_product[node];lazy_product[rson]*=lazy_product[node];

     lazy_sum[lson]*=lazy_product[node];lazy_sum[rson]*=lazy_product[node];

     lazy_sum[lson]+=lazy_sum[node];lazy_sum[rson]+=lazy_sum[node];

     lazy_sum[lson]%=p;lazy_sum[rson]%=p;

     lazy_product[lson]%=p;lazy_product[rson]%=p;

     lazy_sum[node]=;lazy_product[node]=;

 }

 void add(int node,int l,int r,int x,int y,int val){

     if(x==l&&r==y){tree[node]+=(r-l+)*val,tree[node]%=p,lazy_sum[node]+=val;return;}

     int mid=(l+r)>>;pushdown(node,l,r,mid);

     if(y<=mid)add(lson,l,mid,x,y,val);

     else if(x>=mid+)add(rson,mid+,r,x,y,val);

     else{add(lson,l,mid,x,mid,val);add(rson,mid+,r,mid+,y,val);}

     tree[node]=tree[lson]+tree[rson];tree[node]%=p;

 }

 void product(int node,int l,int r,int x,int y,int val){

     if(x==l&&r==y){tree[node]*=val;tree[node]%=p;lazy_product[node]*=val;lazy_product[node]%=p;

         lazy_sum[node]*=val;lazy_sum[node]%=p;return;

     }int mid=(l+r)>>;pushdown(node,l,r,mid);

     if(y<=mid)product(lson,l,mid,x,y,val);

     else if(x>=mid+)product(rson,mid+,r,x,y,val);

     else product(lson,l,mid,x,mid,val),product(rson,mid+,r,mid+,y,val);

     tree[node]=tree[lson]+tree[rson];tree[node]%=p;

 }

 ll find(int node,int l,int r,int x,int y){

     if(x==l&&r==y)return tree[node]%p;

     int mid=(l+r)>>;pushdown(node,l,r,mid);

     if(y<=mid)return find(lson,l,mid,x,y);

     if(x>=mid+)return find(rson,mid+,r,x,y);

     return (find(lson,l,mid,x,mid)+find(rson,mid+,r,mid+,y))%p;

 }

 int main(){cin>>n>>m>>p;

     for(int i=;i<=n;i++)scanf("%d",&s[i]);

     build(,,n);

     for(int i=;i<=m;i++){int a;cin>>a;

         if(a==){int x,y,k;

             scanf("%d%d%d",&x,&y,&k);

             product(,,n,x,y,k);

         }if(a==){int x,y,k;

             scanf("%d%d%d",&x,&y,&k);

             add(,,n,x,y,k);

         }if(a==){int x,y;

             scanf("%d%d",&x,&y);

             cout<<find(,,n,x,y)%p<<endl;

         }

     }return ;

 }