#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int h[N],n,k,cnt;
//h存放元素 n要输入的元素个数 cnt当前堆内元素个数
int p;//p决定堆的类型 p=0小根堆 p=1大根堆
// 要注意的是
// 对序列进行升序排列用大根堆!
// 对序列进行降序排列用小根堆!
void down(int u){
int t=u;
if (u*2<=cnt&&((h[u*2]<h[t])^p)) t=u*2;
if (u*2+1<=cnt&&((h[u*2+1]<h[t])^p)) t=u*2+1;
if (t!=u){
swap(h[t],h[u]);
down(t);
}
}
void up(int u){
while (u>1&&((h[u]<h[u/2])^p)){
swap(h[u],h[u/2]);
u/=2;
}
}
void heap_init(int type,int x){
//初始化函数 确定堆的类型,堆的元素个数 最后调整好各元素位置
p=type;//堆的类型
cnt=x;//堆的元素个数
for (int i=n/2;i>=1;i--){
down(i);
}
}
void push(int x){
//插入元素 最后一个位置加入 up上去
h[++cnt]=x;
up(cnt);
}
void kill(int u){
//删除元素 把目标元素替换成最后一个元素 然后总元素数-1
//最后调整位置
swap(h[u],h[cnt]);
cnt--;
down(u),up(u);
}
void replace(int u,int x){
//修改元素 把目标元素替换成想要的值 然后总元素数个数不变
//最后调整位置
h[u]=x;
down(u),up(u);
}
void heap_sort(int h[],int &cnt){
//堆排序函数 核心思想就是弹出堆顶后,将最后一个元素换到堆顶,然后down下去
int t=cnt;
for (int i=cnt;i>=1;i--){
swap(h[i],h[1]);
cnt--;//因为已经弹出堆顶了 堆内元素数-1
down(1);
}
cnt=t;
}
int main (){
scanf ("%d%d",&n,&k);
for (int i=1;i<=n;i++){
int x;
scanf ("%d",&h[i]);
}
heap_init(1,n);//我要升序输出 所以要选择大根堆
heap_sort(h,cnt);
for (int i=1;i<=n;i++){
printf ("%d ",h[i]);
}
puts("");
heap_init(1,n);
//因为进行了一次排序,此时堆内元素已经不是按照初始类型存放了
//所以要初始化一次
kill(1);//删掉堆顶元素5
for (int i=1;i<=cnt;i++){
printf ("%d ",h[i]);
}
puts("");
replace(1,10);//替换堆顶元素4为10
for (int i=1;i<=cnt;i++){
printf ("%d ",h[i]);
}
puts("");
heap_sort(h,cnt);
for (int i=1;i<=cnt;i++){
printf ("%d ",h[i]);
}
puts("");
return 0;
}