#include <iostream>
#include <bits/stdc++.h>
#include <conio.h>
using namespace std;

const int NMAX=1000;

int DHeap[NMAX];

int n=0,d;
///O(log(d->n))
void FixUp(int x)
{
    int p=(x-1)/d;
    while(x!=0 && DHeap[p]>DHeap[x]) {
        swap(DHeap[p],DHeap[x]);
        x=p;
        p=(n-1)/d;
    }
};

void Add() {
    int x;
    cin>>x;
    DHeap[n]=x;
    FixUp(n);
    n++;
};

void Output() {
    cout<<DHeap[0];
    for(int i=1; i<n; ++i) {
        if(i%d==1) cout<<endl;
        cout<<DHeap[i]<<' ';
    }
    cout<<endl;
    system("pause");
};

int minchild(int x) {
    if(x*d+1>=n) return -1;
    int lastson=(x+1)*d,minson=x*d+1;
    if(lastson>=n) lastson=n-1;
    int firstson=x*d+1;
    for(int i=firstson; i<=lastson; ++i) {
        if(DHeap[i]<DHeap[minson])
            minson=i;
    }
    return minson;

}
///O(d*log(d->n))
void FixDown(int x) {
    int mi=minchild(x);
    if(mi!=-1) {
    //cout<<x<<' '<<mi<<endl;
    if(x<n && DHeap[x]>DHeap[mi]) {
        swap(DHeap[x],DHeap[mi]);
        FixDown(mi);
    }
    }
};

void Increase_key() {
    int x,i;
    cin>>i>>x;
    DHeap[i]+=x;
    FixDown(i);

};
///O(log(d->n)+n-n/d)==O(n)
void Extract_Max() {
    int maxi=0;
    int pow=1,leaf=0;
    while(leaf<n) {
        pow*=d;
        leaf+=pow;
    }
    for(int i=leaf-pow; i<n; ++i) {
        if(DHeap[i]>DHeap[maxi]) maxi=i;
    }
    cout<<DHeap[maxi];
    system("pause");
};


int MainMenu() {
	int key = 0;
	int code;
	do {
		system("cls");
		key = (key + 5) % 5;
		if (key == 0) cout << "-> Add next num" << endl;
		else  cout << "   Add next num" << endl;
		if (key == 1) cout << "-> Output matrix" << endl;
		else  cout << "   Output matrix" << endl;
		if (key == 2) cout << "-> Extract_Max" << endl;
		else  cout << "   Extract_Max" << endl;
		if (key == 3) cout << "-> Increase_Key" << endl;
		else  cout << "   Increase_Key" << endl;
		if (key == 4) cout << "-> Exit" << endl;
		else  cout << "   Exit" << endl;
		code = _getch();
		if (code == 224)
		{
			code = _getch();
			if (code == 80) key++;
			if (code == 72) key--;
		}
	} while (code != 13);
	system("cls");
	return key;
}

int main()
{
    cin>>d;
    for (;;) {
		int answer = MainMenu();
		switch (answer)
		{
		case 0: Add(); break;
		case 1: Output(); break;
		case 2: Extract_Max(); break;
		case 3: Increase_key(); break;
		case 4: return 0;
		}
	}
    return 0;
}