#include<iostream>
using namespace std;

struct Node{
	int key;
	Node * prior;
	Node * next;
};

int power(int n,int t){
	int x = n;
	while(--t)x*=n;
	return x;
}

Node* createNode(int n){
	Node *p;
	if((p = new Node())==NULL){
		cout<<"無法分配內存！"<<endl;
	}
	p->key = n;
	p->prior = NULL;
	p->next = NULL;
	return p;
}

void viewAllNodes(Node *L){
	Node *h = L->next;
	while(h!=L){
		cout<<h->key<<" ";
		h = h->next;		
	};
	cout<<endl;
}

template<class Type>
void radix_sort(Type *L, int k){
	Type *Lhead[10], *p;
	int i,j;
	for(i=0; i<10; i++){
		Lhead[i] = new Type;
	}
	for(i=0; i<k; i++){
		for(j=0; j<10; j++){
			Lhead[j]->prior = Lhead[j] -> next = Lhead[j];
		}
		while(L->next!=L){
			p = del_entry(L);
			j = get_digital(p,i);
			add_entry(Lhead[j], p);
		}
		for(j=0;j<10;j++){
			append(L,Lhead[j]);
		}
	}
	for(i=0; i<10; i++){
		delete(Lhead[i]);
	}
}

template <class Type>
Type *del_entry(Type *L){
	Type *p;
	p = L->next;
	if(p!=L){
		p->prior->next = p->next;
		p->next->prior = p->prior;
	}
	else {
		p = NULL;
	}
	return p;
}

template <class Type>
void add_entry(Type *L, Type *p){
	p->prior = L->prior;
	p->next = L;
	L->prior->next = p;
	L->prior = p;
}

template <class Type>
int get_digital(Type *p, int i){
	int key;
	key = p->key;
	if(i!=0){
		key = key/power(10,i);
	}
	return key%10;
}

template<class Type>
void append(Type *L, Type* L1){
	if(L1->next!=L1){
		L->prior->next = L1 ->next;
		L1->next->prior = L->prior;
		L1->prior->next = L;
		L->prior = L1->prior;
	}
}

int main(){
	Node *h,*p;
	int n,k, value;

	cout<<"請輸入數組的長度：";
	cin>>n;
	cout<<"請輸入數組元素的最多位數：";
	cin>>k;
	cout<<"請輸入數組元素：";
	h = createNode(0);
	h->next = h->prior = h;
	for(int i=0;i<n;i++){
		cin>>value;
		p = createNode(value);
		add_entry(h,p);
	}
	radix_sort(h,k);
	viewAllNodes(h);
	return 0;
}