template<typename T>
    inline void swap(T& x,T& y)
    {
        T t = std::move(x);
        x = std::move(y);
        y = std::move(t);
    }

    template<typename iterator>
    inline iterator median(iterator& first,iterator& last)
    {
        iterator center=first+(last-first)/2;

        if(*center<*first){
            if(*first<*(last-1))
                STL::swap(*first,*(last-1));
            else if(*(last-1)<*center)
                STL::swap(*center,*(last-1));
            else
                return (last-1);
        }
        else{
            if(*(last-1)<*first)
                STL::swap(*first,*(last-1));
            else if(*center<*(last-1))
                STL::swap(*center,*(last-1));
            else
                return (last-1);
        }
        return (last-1);
    }

    

    template<typename iterator>
    inline iterator partition(iterator& first,iterator& last)
    {
        iterator div=median(first,last);
        iterator i=first-1;
        iterator j=last-1;
        for(;;)
        {
            while(*(++i)<*div);
            while(*(--j)>*div);
            if(i<j)
                STL::swap(*i,*j);
            else
                break;
        }
        STL::swap(*i,*(last-1));

        return i;
    }

   

    template<typename iterator>
    void quick_sort(iterator first,iterator last)
    {
        if(last-first<=1)
            return ;
        iterator i=partition(first,last);
        quick_sort(first,i);
        quick_sort(i+1,last);
    }