// by TheSky233 (www.luogu.com.cn/user/501865)
// 转载请标明出处 qwq
#include <bits/stdc++.h>
using namespace std;

template<typename T> T readIn(){
	T x(0),f(0);
	char ch=getchar();
	while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return f?-x:x;
}

template<typename T> void write(T x){
	static char buf[64];
	static int tot(0);
	if(x<0) putchar('-'),x=-x;
	do buf[++tot]=(x%10)+48,x/=10; while(x);
	do putchar(buf[tot--]); while(tot);
}

const int N=1e6+5;
int n, arr[N], len;

class Sort{
	private:
		int a[N];
	public:
		void readArray(){
			n=readIn<int>();
			for(int i=1;i<=n;i++) a[i]=readIn<int>();
		}
		
		void writeArray(){
			for(int i=1;i<=n;i++) write(a[i]),putchar(' ');
		}
		
		void SelectionSort(){
			for(int i=1;i<=n;i++){
				int k=0,arr=(1<<30);
				for(int j=i;j<=n;j++)
					if(a[j]<arr) arr=a[j],k=j;
				swap(a[i],a[k]);
			}
		}
		
		void BubbleSort(){
			for(int i=1;i<=n;i++){
			    bool flag=0;
				for(int j=i+1;j<=n;j++)
					if(a[i]>a[j]) swap(a[i],a[j]),flag=1;
			    if(!flag) break;
			}
        }
		
		void InsertionSort(){
			for(int i=1;i<=n;i++){
				int k=a[i];
				for(int j=i-1;j>=1;j--){
					if(a[j]>k) swap(a[j],a[j+1]);
					else break;
				}
			}
		}
		
		void ShellSort(){
			int gap=1;
			while(gap<n) gap=gap*3+1;
			while(gap>=1){
				for(int i=gap;i<=n;i++)
					for(int j=i;j>=gap && a[j]<a[j-gap]; j-=gap)
						swap(a[j],a[j-gap]);
				gap/=3;
			}
		}
		
		void QuickSort(int L,int R){
			int tmp=a[(L+R)>>1],i=L,j=R;
			do{
				while(a[i]<tmp) i++;
				while(a[j]>tmp) j--;
				if(i<=j) swap(a[i],a[j]),i++,j--;
			}while(i<=j);
			if(i<R) QuickSort(i,R);
			if(j>L) QuickSort(L,j);
		}
		
		void Merge(int l,int mid,int r,int *c){
			int i=l,j=mid+1;
			int L=mid,R=r;
			int k=0;
			while(i<=L && j<=R){
				if(a[i]<a[j]) c[++k]=a[i++];
				else c[++k]=a[j++];
			}
			while(i<=L) c[++k]=a[i++];
			while(j<=R) c[++k]=a[j++];
			for(int i=1;i<=k;i++) a[l+i-1]=c[i];
		}
		
		void MergeSort(int l,int r){
			if(l>r || l==r) return;
			int mid=(l+r)>>1;
			MergeSort(l,mid);
			MergeSort(mid+1,r);
			Merge(l,mid,r,arr);
		}
		
		void put(int x){
			arr[++len]=x;
			int p=len;
			while(p!=1&&arr[p/2]>arr[p]){
				swap(arr[p],arr[p/2]);
				p/=2;
			} 
		}
		
		int get(){
			int p=1,q;
			int x=arr[1]; arr[1]=arr[len]; len--;
			while(p*2<=len){
				if(p*2+1>len||arr[p*2]<arr[p*2+1]) q=p*2;
				else q=p*2+1;
				if(arr[p]>arr[q]){
					swap(arr[p],arr[q]);
					p=q;
				}
				else return x;
			}
			return x;
		}
		
		void HeapSort(){
			for(int i=1;i<=n;i++) put(a[i]);
			for(int i=1;i<=n;i++) a[i]=get();
		}
		
		void CountingSort(){
			int l=a[min_element(a+1,a+n+1)-a];
			int r=a[max_element(a+1,a+n+1)-a];
			int k=r-l+1;
			int c[k+5]={0};
			for(int i=1;i<=n;i++) c[a[i]-l]++;
			int tot=0;
			for(int i=0;i<=k;i++)
				for(int j=1;j<=c[i];j++)
					a[++tot]=i+l;
		}
		
		void BucketSort(){
			vector<int> bucket[n];
			int bucket_size=a[max_element(a+1,a+n+1)-a]/n+1,p=0;
			for(int i=0;i<n;i++) bucket[i].clear();
			for(int i=1;i<=n;i++) bucket[a[i]/bucket_size].push_back(a[i]);
			for(unsigned int d=0;d<n;d++){
				for(int i=0;i<bucket[d].size();i++){
					int k=bucket[d][i];
					for(int j=i-1;j>=0;j--){
						if(bucket[d][j]>k) swap(bucket[d][j],bucket[d][j+1]);
						else break;
					}
				}
				for(unsigned int i=0;i<bucket[d].size();i++) a[++p]=bucket[d][i];
			}
		}
		
		void RadixSort(){
			int d=(int)log10(a[max_element(a+1,a+n+1)-a])+1;
			int cnt[10],radix=1;
			for(int i=1;i<=d;i++){
				for(int j=0;j<10;j++) cnt[j]=0;
				for(int j=1;j<=n;j++){
					int k=(a[j]/radix)%10;
					cnt[k]++;
				}
				for(int j=1;j<10;j++) cnt[j]+=cnt[j-1];
				for(int j=n;j>=1;j--){
					int k=(a[j]/radix)%10;
					arr[cnt[k]]=a[j];
					cnt[k]--;
				}
				for(int j=1;j<=n;j++) a[j]=arr[j];
				radix*=10;
			}
		}
}Array;

int opt;

int main(){
	Array.readArray();
	opt=readIn<int>();
	switch(opt){
		case 1: {Array.SelectionSort(); break;}
		case 2: {Array.BubbleSort(); break;}
		case 3: {Array.InsertionSort(); break;}
		case 4: {Array.ShellSort(); break;}
		case 5: {Array.QuickSort(1,n); break;}
		case 6: {Array.MergeSort(1,n); break;}
		case 7: {Array.HeapSort(); break;}
		case 8: {Array.CountingSort(); break;}
		case 9: {Array.BucketSort(); break;}
		case 10: {Array.RadixSort(); break;}
	}
	Array.writeArray();
}