Untitled

// cay nhi phan ly tuong
/*
#include <bits/stdc++.h>
using namespace std;
struct treenode
{
    int data;
    treenode* left;
    treenode* right;
    treenode(int data):data(data),left(NULL),right(NULL){};
};
void insert(treenode*& root,int data)
{
    if(!root)
    {
        root=new treenode(data);
    }
    else{
        if(data<root->data)
        {
            insert(root->left,data);
        }
        else{
            insert(root->right,data);
        }
    }
}
bool isspecial(treenode* node,int level,int leaflevel)
{
    if(!node)
        return true;
    if(node->left==NULL && node->right==NULL)
    {
        if(leaflevel==-1){
            leaflevel=level;
            return true;
        }
        return (level==leaflevel);
    }

    if(node->left==NULL || node->right==NULL)
        return false;
    return  isspecial(node->left,level+1,leaflevel)&&
            isspecial(node->right,level+1,leaflevel);
}
bool hehe(treenode* root)
{
    if(root==nullptr)
        return true;
    int leaflevel=-1;
    return isspecial(root,0,leaflevel);
}
int main()
{
    treenode* root=NULL;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        insert(root,x);
    }
    if(hehe(root))
        cout<<"Yes";
    else cout<<"No";
}
*/
//diem gan goc toan do
/*
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
    node* next;
    node(int x,int y):x(x),y(y),next(nullptr){};
};
node* insertbruh(node* head,int x,int y)
{
    node* we=new node(x,y);
    if(head==nullptr||(head->x*head->x+head->y*head->y)>(we->x*we->x+we->y*we->y)||(head->x*head->x+head->y*head->y)==(we->x*we->x+we->y*we->y)&&(head->x>we->x))
    {
        we->next=head;
        return we;
    }
    node* temp=head;
    while(temp->next!=nullptr){
        if((temp->next->x*temp->next->x+temp->next->y*temp->next->y)<(we->x*we->x+we->y*we->y))
        {
            temp=temp->next;
        }
        else if((temp->next->x*temp->next->x+temp->next->y*temp->next->y)==(we->x*we->x+we->y*we->y)&&(temp->next->x<we->x))
        {
            temp=temp->next;
        }
    }
    we->next=temp->next;
    temp->next=we;
    return head;
}
void print(node* head)
{
    node* bru=head;
    while(bru)
    {
        cout<<bru->x<<" "<<bru->y<<endl;
        bru=bru->next;
    }

}
int main()
{
    int n;
    cin>>n;
    node* head=nullptr;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        head=insertbruh(head,x,y);//mistake;
    }
    print(head);
}
*/
//
/*
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,z;
    node* next;
    node(int x,int y,int z):x(x),y(y),z(z),next(nullptr){};
};
node* insert(node*& head,int x,int y,int z)
{
    node* newnode=new node(x,y,z);
    if(head==nullptr)
    {
        newnode->next=head;
        return newnode;
    }
    node*temp=head;
    while(temp->next!=nullptr)
    {
        temp=temp->next;
    }
    temp->next=newnode;
    return head;
}
int vitriphathien(node* head,int x,int y, int z)
{
    int value=0;
    node* temp=head;
    while(temp)
    {
        if(temp->x==x&&temp->y==y&&temp->z==z)
        return value;
        value++;
        temp=temp->next;
    }
    return -1;

}
int main()
{
    int n;
    cin>>n;
    node* head=nullptr;
    for(int i=0;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        head=insert(head,x,y,z);
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        int vitriphathien1=vitriphathien(head,x,y,z);
        if(vitriphathien1!=-1)
        {
            cout<<vitriphathien1<<endl;
        }
        else cout<<"KHONG"<<endl;
    }
}
*/
//bang bam don gian
/*
#include <bits/stdc++.h>
using namespace std;
int hashh(int key,int m)
{
    return key%m;
}
int rehash(int key,int m,int i)
{
    return(hashh(key,m)+(i*i))%m;
}
int main()
{
    int m,n;
    cin>>m>>n;
    int* hashtable=new int[m];
    for(int i=0;i<m;i++)
    {
        hashtable[i]=0;
    }
    int* a=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        int x=a[i];
        int j=0;
        while(j<m)
        {
            int pos=rehash(x,m,j);
            if(hashtable[pos]==0||hashtable[pos]==-1)
            {
                hashtable[pos]=x;
                break;
            }
            j++;
        }
        if(j==m)
            {cout<<x<<" FULL"<<endl;}
    }
    for(int i=0;i<m;i++)
    {
        if(hashtable[i]==0)
        {
            cout<<i<<endl;
        }
    }
    delete[] hashtable;
    delete[] a;
}
*/
//tim kiem nhi phan
/*
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    double x, y, z;
};

bool operator==(const Point& p1, const Point& p2) {
    return p1.x == p2.x && p1.y == p2.y && p1.z == p2.z;
}

bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) return p1.x < p2.x;
    if (p1.y != p2.y) return p1.y < p2.y;
    return p1.z < p2.z;
}

int binarySearch(const Point A[], int n, const Point& key) {
    int left = 0;
    int right = n - 1;
    int comparisons = 0;

    while (left <= right) {
        comparisons++;
        int mid = left + (right - left) / 2;

        if (A[mid] == key) {
            return comparisons;
        }
        if (A[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    int n;
    cin >> n;
    Point* A = new Point[n];

    // Nhập danh sách A và lưu vào mảng
    for (int i = 0; i < n; ++i) {
        cin >> A[i].x >> A[i].y >> A[i].z;
    }

    //sort(A, A + n); // Sắp xếp mảng A theo thứ tự tăng dần

    int m;
    cin >> m;
    Point* pi = new Point[m];

    // Nhập các điểm pi cần kiểm tra
    for (int i = 0; i < m; ++i) {
        cin >> pi[i].x >> pi[i].y >> pi[i].z;
    }

    // Kiểm tra từng điểm pi trong mảng pi
    for (int i = 0; i < m; ++i) {
        int comparisons = binarySearch(A, n, pi[i]);
        if (comparisons == -1) {
            cout << "KHONG" << endl;
        } else {
            cout << comparisons << endl;
        }
    }

    delete[] A;
    delete[] pi;

    return 0;
}
*/
//tim node xa node goc nhat
/*
#include<bits/stdc++.h>
using namespace std;
struct treenode
{
    int data;
    treenode* left;
    treenode* right;
    treenode(int data):data(data),left(nullptr),right(nullptr){};
};
void insert(treenode*& root,int x)
{
    if(root==nullptr)
    {
        root=new treenode(x);
        return;
    }
    if(root->data>x)
    {
        insert(root->left,x);
    }
    else
        insert(root->right,x);
}
int maxdepth(treenode* root)
{
    if(root==nullptr)
        return -1;
    return 1+max(maxdepth(root->left),maxdepth(root->right));
}
void thuthapnode(treenode* root,int currentdepth,int maxdepth,vector<treenode*>& deeppestnodes)
{
    if(root==nullptr) return;
    if(currentdepth==maxdepth)
        deeppestnodes.push_back(root);
    thuthapnode(root->left,currentdepth+1,maxdepth,deeppestnodes);
    thuthapnode(root->right,currentdepth+1,maxdepth,deeppestnodes);
}
vector<treenode*>deep(treenode* root)
{
    int maxdep=maxdepth(root);
    vector<treenode*>deepestnodes;
    thuthapnode(root,0,maxdep,deepestnodes);
    return deepestnodes;
}
int main()
{
    int n;
    cin>>n;
    treenode* root=nullptr;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        insert(root,x);
    }
    vector<treenode*>vietnam=deep(root);
    for(treenode* x:vietnam)
    {
        cout<<x->data<<" ";
    }
}
*/
//thao tac voi danh sach lien ket
/*
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node* next;
    node(int data):data(data),next(nullptr){};
};
node* pushfront(node*& head,int data)
{
    node* newnode=new node(data);
    newnode->next=head;
    head=newnode;
    return head;
}
node* pushback(node*& head,int data)
{
    node* newnode=new node(data);
    if(head==nullptr)
        {
            pushfront(head,data);
            return head;
        }
    node* temp=head;
    while(temp->next!=nullptr)
    {
        temp=temp->next;
    }
    temp->next=newnode;
    return head;
}
node* deletefirst(node* head)
{
    if(head==nullptr)
        return head;
    head=head->next;
    return head;

}
void deletelast(node*& head)
{
    if(head==nullptr)
    return ;
    node* before=nullptr;
    node* after=head;
    while(after->next)
    {
        before=after;
        after=after->next;
    }
    if(before==nullptr)
    {
        delete head;
        head=nullptr;
    }
    else
    {
        before->next=nullptr;
        delete after;
    }

}
int sizee(node* head)
{
    int dem=0;
    node* p=head;
    while(p)
    {
        dem++;
        p=p->next;
    }
    return dem;
}
void deletemiddle(node*& head,int vitri)
{
    int n=sizee(head);
    if(vitri<0||vitri>n-1)
    {
        cout<<"No position"<<endl;
        return;
    }
    if(vitri==0)
    {
        head=deletefirst(head);
        return;
    }
    if(vitri==n-1)
    {
        deletelast(head);
        return;
    }

        node* prev=nullptr;
        node* current=head;

    for(int i=0;i<vitri;i++)
    {
        prev=current;
        current=current->next;
    }
    if(prev==nullptr)
    {
        head=current->next;

    }
    else
    {
        prev->next=current->next;
        delete current;
    }

}

node* pushmiddle(node*& head,int data,int vitri)
{
    int n=sizee(head);
    if(vitri<0||vitri>n-1)
    {
        cout<<"No position";
    }
    if(vitri==0)
    {
        pushfront(head,data);
        return head;
    }
    if(vitri==n-1)
    {
        pushback(head,data);
    }
    node* temp=head;
    for(int i=0;i<vitri;i++)
    {
        temp=temp->next;
    }
    node* newnode=new node(data);
    newnode->next=temp->next;
    temp->next=newnode;
    return head;

}


void print(node* head)
{
    node* temp=head;
    while(temp)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main()
{
    int n;
    cin>>n;
    node* head=nullptr;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        //head=pushfront(head,x);
        head=pushback(head,x);
    }
    head=pushmiddle(head,7,2);
    head=deletefirst(head);
    deletelast(head);
    deletemiddle(head,0);
    print(head);
    //cout<<sizee(head);
}
*/
//bai cay nhi phan
/*
#include <iostream>
using namespace std;
struct treenode
{
    int data;
    treenode* left;
    treenode* right;
    treenode(int data):data(data),left(nullptr),right(nullptr){};
};
void insert(treenode*& root,int key)
{
    if(!root)
        root=new treenode(key);
    else if(key<root->data)
    {
        insert(root->left,key);
    }
    else insert(root->right,key);
}
int maxdepth(treenode* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxdepth(root->left), maxdepth(root->right));
}

int countnodes(treenode* root) {
    if (root == nullptr) return 0;
    return 1 + countnodes(root->left) + countnodes(root->right);
}
void solve(treenode* root)
{
    if(root==nullptr)
        cout<<"Cay khong dat yeu cau";
    else if(maxdepth(root->left)==2*maxdepth(root->right))
    {
        cout<<countnodes(root);
    }
    else cout<<"Cay khong dat yeu cau";
}
int main()
{
    int n;
    cin>>n;
    treenode* root=nullptr;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        insert(root,x);
    }
    solve(root);

}
*/
/*
#include <iostream>
using namespace std;
struct treenode
{
    int data;
    treenode* left;
    treenode* right;
    treenode(int data):data(data),left(nullptr),right(nullptr){};
};
void insert(treenode*& root,int key)
{
    if(!root)
        root=new treenode(key);
    else if(key<root->data)
    {
        insert(root->left,key);
    }
    else insert(root->right,key);
}
void lnr(treenode* root)
{
    if(root==nullptr)
        return;
    lnr(root->left);
    cout<<root->data<<" ";
    lnr(root->right);
}
void nlr(treenode*root)
{
    if(root==nullptr)
        return;
    cout<<root->data<<" ";
    nlr(root->left);
    nlr(root->right);
}
void lrn(treenode* root)
{
    if(root==nullptr)
        return;
    lrn(root->left);
    lrn(root->right);
    cout<<root->data<<" ";
}
int main()
{
    int n;
    cin>>n;
    treenode* root=nullptr;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        insert(root,x);
    }
    lnr(root);
    cout<<endl;
    lrn(root);
    cout<<endl;
    lnr(root);
}
*/
#include <bits/stdc++.h>
using namespace std;
struct student
{
    string name;
    int diem;
    student(string name,int diem):name(name),diem(diem){};

};
struct node
{
    student data;
    node* next;
    node(student data):data(data),next(nullptr){}
};
void insertstudent(node*& head,student s)
{
    node* newnode=new node(s);
    if(head==nullptr){
        head=newnode;
        return;
    }

    node* temp=head;
    while(temp->next)
    {
        temp=temp->next;
    }
    temp->next=newnode;
}
void print9(node* head)
{
    node* hehe=head;
    while(hehe)
    {
        if(hehe->data.diem>9)
        {
            cout<<hehe->data.name<<endl;

        }
        hehe=hehe->next;
    }
}
int main()
{
    int n;
    cin>>n;
    node* head=nullptr;
    for(int i=0;i<n;i++)
    {
        int x;
        string y;
        cin>>x>>y;
        student s(y,x);
        insertstudent(head,s);
    }
    print9(head);
}