//problem-1

#include<bits/stdc++.h>
using namespace std;
void kamrul_insertionsort(int n, string kamrul_a[])
{
    int i, j;
    string key;
    for(int i=1; i<n; i++)
    {
        key=kamrul_a[i];
        j=i-1;
        while(j>=0 && kamrul_a[j]>key)
        {
            kamrul_a[j+1]=kamrul_a[j];
            j=j-1;
        }
       kamrul_a[j+1]=key;
    }

    for (int i=0; i < n; i++)
    {
        cout<<kamrul_a[i]<<"\n";
    }
}



void kamrul_binarysearch(int n, string kamrul_a[])
{
    string element;
    cin>>element;

    int low,high,middle;
    low=0;
    high=n-1;

    while(low<=high)
    {
        middle=(low+high)/2;

        if(kamrul_a[middle]==element)
        {
            cout<<"\n\nsearching item found at index :"<<middle+1;

            return;
        }

        else if(kamrul_a[middle]<element)
        {
            low = middle+1;
        }
        else if(kamrul_a[middle]>element)
        {
            high=middle-1;
        }
    }
       cout<<"Element not found in the data set";

}

void kamrul_delete(int n, string kamrul_a[])
{
    int i,j,k;
    for(i=0; i<n; ++i)
        for(j=i+1; j<n;)
        {
            if(kamrul_a[i]==kamrul_a[j])
            {
                for(k=j; k<n-1; ++k)
                    kamrul_a[k]=kamrul_a[k+1];
                --n;
            }
            else
                ++j;

        }

    cout<<"\n";
    for(i=0; i<n; ++i)
        cout<<kamrul_a[i]<<" ";

}

int main()
{
    int n;
    cout<<"Enter the size of array : ";
    cin>>n;
    cout<<"Enter the Array : \n";
    string a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    cout<<"\n\nSorting elements are:"<<endl;
    kamrul_insertionsort(n, a);
     cout<<"\n\n Enter search element:"<<endl;
   kamrul_binarysearch(n, a);
    cout<<"\n\n deleting all duplicate elements:"<<endl;
    kamrul_delete(n, a);
    cout<<endl;


}



//problem-2
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string arr[50];
int x;

bool kamrul_compare(string a, string b)
 { return (a.length() <= b.length()); }

void kamrul_split(string word)
{
 int size = word.length();
 int i = 0, x = 0, j = 0;
 string s;

 while(i <= size)
 {
  if(word[i] == ' ' || word[i] == '\0'){
   s = word.substr(j, i - j);
   arr[x] = s;
   j = i + 1;
   x++;
  }
  i++;
 }

 stable_sort(arr, arr + x, kamrul_compare);
 reverse(arr, arr + x);

 for (i = 0; i < x; ++i)
 {
  cout << arr[i];
  if(i != (x - 1))
   cout << " ";
 }

 cout << endl;
}

int main(int argc, char const *argv[])
{
 int n, i;
 string word;

 cin >> n;
  cin.ignore();

 while(n--)
 {
  getline(cin, word);
  kamrul_split(word);
 }

 return 0;
}