> #include <iostream>
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> #include <string>
> #include <algorithm>
> #include <cmath>
> #define M 1000000
> using namespace std;
> int n,m,a[M+1];
> 
> struct node{int pos,val;}q[M+1];
> 
> void getmin()
> {
> 	int head=0,tail=-1;
> 	for (register int i=0;i<m-1;i++)
> 	{
> 		while (head<=tail&&q[tail].val>a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 	}
> 	for (register int i=m-1;i<n;i++)
> 	{
> 		while (head<=tail&&i-q[head].pos>=m) head++;
> 		while (head<=tail&&q[tail].val>a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 		printf("%d ",q[head].val);
> 	}
> 	printf("\n");
> }
> 
> void getmax()
> {
> 	int head=0,tail=-1;
> 	for (register int i=0;i<m-1;i++)
> 	{
> 		while (head<=tail&&q[tail].val<a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 	}
> 	for (register int i=m-1;i<n;i++)
> 	{
> 		while (head<=tail&&i-q[head].pos>=m) head++;
> 		while (head<=tail&&q[tail].val<a[i]) tail--;
> 		q[++tail].val=a[i],q[tail].pos=i;
> 		printf("%d ",q[head].val);
> 	}
> 	printf("\n");
> }
> 
> int main()
> {
> 	scanf("%d%d",&n,&m);
> 	for (register int i=0;i<n;i++) scanf("%d",&a[i]);
> 	getmin(),getmax();
> 	return 0;
> }