#include<bits/stdc++.h>
#define maxn 10007
#define oo 1000000007
#define ld long double
#define ll long long
#define FOR(i,a,b) for(long i=(a), _i=(b); i<=_i;i++)
#define FORD(i,b,a) for(long i=(b), _i=(a); i>=_i;i--)

using namespace std;

typedef struct Node{
	char* MaSV;
	char* Hoten;
	ld Diem;
	struct Node *left = NULL, *right = NULL;
} Node;

Node* Head = NULL;
Node* Tail = NULL;

Node* creatNode(char* Ma, char* Ten, ld diem){
	Node* N;
	int len;
	N = new Node;
	len = strlen(Ma);
	N->MaSV = new char[len];
	N->MaSV = strcpy(N->MaSV, Ma);
	len = strlen(Ten);
	N->Hoten = new char[len];
	N->Hoten = strcpy(N->Hoten, Ten);
	N->Diem = diem;
	return N;
}
int insertList(Node* N){
	Node* M;
	if (Head == NULL ){
		Head = N;
		Tail = N;
		return 0;
	}
	M = Tail;
	M->right = N;
	N->left = M;
	Tail = N;
	return 0;
}

int creatDS(){
	ll n;
	Node* N;
	char* Ma;
	char* Ten;
	ld diem;
	cout << "Tao moi DS" << endl;
	cin >> n;
	FOR(i,0,n-1){
		cin.ignore(1);
		Ma = new char[255];
		cin.getline(Ma, 255);
		Ten = new char[255];
		cin.getline(Ten, 255);
		cin >> diem;
		N = creatNode(Ma, Ten, diem);
		insertList(N);
	}
	return 0;
}

int printList(){
	Node* N;
	N = Head;
	while (N!= NULL){
		cout << "Thong tin ve sinh vien co ma " << N->MaSV << endl;
		cout << "Ho ten: " << N->Hoten << endl;
		cout << "Diem trung binh: " << N->Diem << endl << endl;
		N = N->right;
	}
	return 0;
}

int printNode(){
	Node* N;
	char* Ma;
	cin.ignore(1);
	Ma = new char[255];
	cin.getline(Ma, 255);
	N = Head;
	while (N!= NULL){
		if (strcmp(N->MaSV, Ma) == 0) {
			cout << "Sinh vien co ma " << Ma << " nam tai dia chi " << N << endl;
			return 0;
		}
		N = N->right;
	}
	cout << "Sinh vien co ma " << Ma << " khong ton tai!" << endl;
	return 0;
}


int findNode(){
	Node* N;
	char* Ma;
	cin.ignore(1);
	Ma = new char[255];
	cin.getline(Ma, 255);
	N = Head;
	while (N!= NULL){
		if (strcmp(N->MaSV, Ma) == 0) {
			cout << "Thong tin ve sinh vien co ma " << Ma << " :\n";
			cout << "Ho ten: " << N->Hoten << endl;
			cout << "Diem trung binh: " << N->Diem << endl;
			return 0;
		}
		N = N->right;
	}
	cout << "Sinh vien co ma " << Ma << " khong ton tai!" << endl;
	return 0;
}

int deleteNode(){
	Node* N;
	char* Ma;
	cin.ignore(1);
	Ma = new char[255];
	cin.getline(Ma, 255);
	N = Head;
	if (strcmp(N->MaSV, Ma) == 0) {
		N->right->left = NULL;
		Head = N->right;
		if (Head == NULL) Tail == NULL;
		delete N;
		return 0;
	}
	N = Tail;
	if (strcmp(N->MaSV, Ma) == 0) {
		N->left->right = NULL;
		Tail = N->left;
		if (Head == NULL) Tail == NULL;
		delete N;
		return 0;
	}
	N = Head->right;
	while (N->right!= NULL){
		if (strcmp(N->MaSV, Ma) == 0) {
			N->left->right=N->right;
			N->right->left=N->left;
			delete N;
			return 0;
		}
		N = N->right;
	}
	cout << "Sinh vien co ma " << Ma << " khong ton tai!" << endl;
	return 0;
}

int insertNode(){
	Node *M;
	Node* N;
	char* Ma;
	char* Maleft;
	char* Ten;
	ld diem;
	cin.ignore(1);
	Ma = new char[255];
	cin.getline(Ma, 255);
	Ten = new char[255];
	cin.getline(Ten, 255);
	cin >> diem;
	N = creatNode(Ma, Ten, diem);
	cin.ignore(1);
	Maleft = new char[255];
	cin.getline(Maleft, 255);

	if (strcmp(Maleft,"NULL") == 0) {
		M = Head;
		M->left = N;
		N->right = M;
		Head = N;
		return 0;
	}
	M = Head;
	while (M!= NULL){
		if (strcmp(M->MaSV, Maleft) == 0) {
			if (M == Tail) {
				M->right = N;
				N->left= M;
				Tail = N;
			}
			else {
				M->right->left = N;
				N->right = M->right;
				M->right = N;
				N->left = M;
			}
			return 0;
		}
		M = M->right;
	}
	return 0;
}

int sortList(){
	Node* N;
	Node* M;
	Node* tmp;
	N = Head;
	while (N->right!=NULL){
		M = N->right;
		while (M!=NULL){
			if (N->Diem>M->Diem){
				tmp = M;
				M->Diem = N->Diem;
				N->Diem = tmp->Diem;
				M->MaSV = strcpy(M->MaSV, N->MaSV);
				N->MaSV = strcpy(N->MaSV, tmp->MaSV);
				M->Hoten = strcpy(M->Hoten, N->Hoten);
				N->Hoten = strcpy(N->Hoten, tmp->Hoten);
			}
			M=M->right;
		}
		N=N->right;
	}
	return 0;
}

int main(){
	int menu;
	while (1){
		cin >> menu;
		switch(menu) {
			case 1: {
				creatDS();
				break;
			}
			case 2: {
				cout << "In DS" << endl;
				printList();
				break;
			}
			case 3: {
				cout << "Tim kiem SV" << endl;
				printNode();
				break;
			}
			case 4: {
				cout << "In thong tin SV" << endl;
				findNode();
				break;
			}
			case 5: {
				cout << "Chen SV" << endl;
				insertNode();
				break;
			}
			case 6: {
				cout << "Xoa SV" << endl;
				deleteNode();
				break;
			}
			case 7: {
				cout << "Sap xep DS" << endl;
				sortList();
				break;
			}
			default: exit(0);
		}
	}
	return 0;
}