其实只要算trunc(ln(p)/ln(2))的长度就行了，所以可以不断滚动数组。空间就不会爆掉了。
var n,k,i,j,t,p:longint;
    a,f:Array [0..1000001] of longint;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

function min(a,b:longint):longint;
begin
  if a>b then exit(b) else exit(a);
end;

begin
  readln(n,p);
  for i:=1 to n do
    begin
      read(a[i]);
      f[i]:=a[i];
    end;

  t:=trunc(ln(p)/ln(2));
  for i:=1 to t do
    for j:=1 to n do
      if j+1 shl (i-1)<=n then
        f[j]:=min(f[j],f[j+1 shl (i-1)]);

  for i:=1 to n-p+1 do write(min(f[i],f[i+p-1 shl t]),' ');
  writeln;

  for i:=1 to n do f[i]:=a[i];
  for i:=1 to t do
    for j:=1 to n do
      if j+1 shl (i-1)<=n then
        f[j]:=max(f[j],f[j+1 shl (i-1)]);

  for i:=1 to n-p+1 do write(max(f[i],f[i+p-1 shl t]),' ');
  writeln;
end.