//template
#include<iostream>
#include<cstdlib>
#include<assert.h>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};

template <class T>
class Minimum_maintenance {
  private:
    T * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
    int * _fakedeepcopy ;
  public:
    Minimum_maintenance(){
      cout<<"NOT SUPPORT"<<endl;
      assert(0);
    }
    Minimum_maintenance(int s){
      if(s < 1)//protect
        s = 1;
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
      _fakedeepcopy = new int [1] ;
      printf("new (%08x)\n",this);
      printf("    _stack[0] = (%08x)\n",_stack[0]);
      printf("    _stack[1] = (%08x)\n",_stack[1]);
      printf("    _order    = (%08x)\n",_order);
      _fakedeepcopy[0] = 0;
    }
    Minimum_maintenance(const Minimum_maintenance& copy){
      _stack[0]   = copy._stack[0];
      _stack[1]   = copy._stack[1];
      _iter [0]   = copy._iter [0];
      _iter [1]   = copy._iter [1];
      _order      = copy._order;
      _fakedeepcopy = copy._fakedeepcopy;
      _fakedeepcopy[0]++;
      printf("Fake deepcopy %08x => %08x\n",&copy,this);
    }
    ~Minimum_maintenance(){
      printf("free(%08x)\n",this);
      printf("    _fakedeepcopy = %d\n",_fakedeepcopy[0]);
      printf("    _stack[0]   = (%08x)\n",_stack[0]);
      printf("    _stack[1]   = (%08x)\n",_stack[1]);
      printf("    _order      = (%08x)\n",_order);
      if(!_fakedeepcopy[0]){
        delete [] _stack[0];
        delete [] _stack[1];
        delete [] _order;
      }else{
        _fakedeepcopy[0]--;
      }
      cout<<"free() finished"<<endl;
    }
    void push(const T & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(T & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
    bool const empty(){
      return _iter[0] == 0;
    }
};

int main(){
  int i;
  Minimum_maintenance<max_select> mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))//mm.empty()
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

// just run
#include<iostream>
#include<cstdlib>
using namespace std;
class MinimumMaintenance {
  private:
    int * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    MinimumMaintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new int[3*s];
      _stack[1] = new int[3*s];
      _order = new int[s];
    }
    ~MinimumMaintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(int p,int d,int v){
      int i;
      if(_iter[0] == 0 || _stack[0][3*(_iter[0] - 1)+2] > v){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][3*_iter[i]    ] = p;
      _stack[i][3*_iter[i] + 1] = d;
      _stack[i][3*_iter[i] + 2] = v;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(int & p,int & d,int &v){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      p = _stack[0][ 3 * _iter[0] - 3];
      d = _stack[0][ 3 * _iter[0] - 2];
      v = _stack[0][ 3 * _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  MinimumMaintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    int in = rand();
    cout<<in<<endl<<"\t";
    mm.push(1,1,in);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    int a,b,c;
    if(mm.top(a,b,c))
      cout<<c<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

//struct
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
};
class Minimum_maintenance {
  private:
    max_select * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new max_select[s];
      _stack[1] = new max_select[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(const max_select & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1].v > ms.v){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(max_select & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  Minimum_maintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

//operator
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};
class Minimum_maintenance {
  private:
    max_select * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new max_select[s];
      _stack[1] = new max_select[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(const max_select & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(max_select & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  Minimum_maintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  } 
  return 0;
}

//template
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};

template <class T>
class Minimum_maintenance {
  private:
    T * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(){
      // CHANGE?
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[1];
      _stack[1] = new T[1];
      _order = new int[1];
    }
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void resize(int s){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
    }
    void push(const T & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(T & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
    bool empty(){
      return _iter[0] == 0;
    }
};
int main(){
  int i;
  Minimum_maintenance<max_select> mm;
  mm.resize(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))//mm.empty()
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  } 
  return 0;
}

//10 - 0.2s
#include<iostream>
using namespace std;

int pt_s;

void ptdemo(unsigned int pt_bits){
  if(pt_bits == (1<<pt_s) - 1)
    return ;
  unsigned int i;
  for(i = 0; i < pt_s ; ++i){
    if( pt_bits & (1<<i) )
      continue ; 
    //cout<<i<<endl;
    int debug = i;
    ptdemo(pt_bits | (1<<i));
  }
  return ;
}
int main(){
  pt_s = 10;
  int v = 0;
  ptdemo(v);
  return 0;
}

//10 - 11.588 
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    stack<pair<vector<int>::iterator,int>>visitstack; // to boost list?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li,const stack<pair<vector<int>::iterator,int>>&vs)
    :left_index(li),visitstack(vs){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      if(iter == left_index.end())
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }

    int getnum(){
      return visitstack.size();
    }

    int const getvalue(){
      return iter != left_index.end() ? *iter : -1;
    }
    void push(){
      if(iter == left_index.end())
        return ;
      visitstack.push(make_pair(iter,*iter));
      left_index.erase(iter);
    }
    void pop(){
      if(visitstack.empty())
        return ;
      pair<vector<int>::iterator,int> p = visitstack.top();
      left_index.insert(p.first,p.second);
      visitstack.pop();
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      return new Permutation_traversal(left_index,visitstack);
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    pt.push();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
    pt.pop();
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

// ,min.cpp use less check
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    stack<pair<vector<int>::iterator,int>>visitstack; // to boost list?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li,const stack<pair<vector<int>::iterator,int>>&vs)
    :left_index(li),visitstack(vs){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }

    int const getvalue(){
      return *iter;
    }
    void push(){
      visitstack.push(make_pair(iter,*iter));
      left_index.erase(iter);
    }
    void pop(){
      pair<vector<int>::iterator,int> p = visitstack.top();
      left_index.insert(p.first,p.second);
      visitstack.pop();
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      return new Permutation_traversal(left_index,visitstack);
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    cout<<pt.getvalue()<<endl;
    pt.push();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
    pt.pop();
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

//10 4.469s
#include<iostream>
#include<vector>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li)
    :left_index(li){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      if(iter == left_index.end())
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }


    int const getvalue(){
      return iter != left_index.end() ? *iter : -1;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      if(iter == left_index.end())
        return NULL;
      vector<int>::iterator tmp_iter = iter;
      int tmp_val = *iter;
      left_index.erase(iter);
      Permutation_traversal * newpt = new Permutation_traversal(left_index);
      left_index.insert(tmp_iter,tmp_val);
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-left_index.size();
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li)
    :left_index(li){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }


    int const getvalue(){
      return *iter;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      vector<int>::iterator tmp_iter = iter;
      int tmp_val = *iter;
      left_index.erase(iter);
      Permutation_traversal * newpt = new Permutation_traversal(left_index);
      left_index.insert(tmp_iter,tmp_val);
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-left_index.size();
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    cout<<pt.getvalue()<<endl;
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

//10 - 0.927s
#include<iostream>
using namespace std;

class Permutation_traversal{
  protected:
    int * left_index; // to boost vector?
    int size;
    int iter;
    Permutation_traversal(){
    }
  public:
    Permutation_traversal(int s)
    :size(s),iter(0){
      left_index = new int[s];
      for(int i=0;i<s;i++){
        left_index[i]=i;
      }
    }
    ~Permutation_traversal(){
      delete [] left_index;
    }
    bool const empty(){
      return size == 0;
    }
    void next(){
      if(iter == size)
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != size;
    }

    int const getvalue(){
      return iter != size ? left_index[iter] : -1;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      if(iter == size)
        return NULL;
      Permutation_traversal * newpt = new Permutation_traversal();
      newpt->left_index = new int[size-1];
      newpt->size = 0;
      newpt->iter = 0;
      for(int it = 0 ; it < size ; ++it){
        if(it == iter)
          continue;
        newpt->left_index[newpt->size++] = left_index[it];
      }
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-size;
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    int * left_index; // to boost vector?
    int size;
    int iter;
    Permutation_traversal(){
    }
  public:
    Permutation_traversal(int s)
    :size(s),iter(0){
      left_index = new int[s];
      for(int i=0;i<s;i++){
        left_index[i]=i;
      }
    }
    ~Permutation_traversal(){
      delete [] left_index;
    }
    bool const empty(){
      return size == 0;
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != size;
    }

    int const getvalue(){
      return left_index[iter];
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      Permutation_traversal * newpt = new Permutation_traversal();
      newpt->left_index = new int[size-1];
      newpt->size = 0;
      newpt->iter = 0;
      for(int it = 0 ; it < size ; ++it){
        if(it == iter)
          continue;
        newpt->left_index[newpt->size++] = left_index[it];
      }
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-size;
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    cout<<pt.getvalue()<<endl;
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

//10 - 0.581s
#include<iostream>
using namespace std;

class Permutation_traversal{
  private:
  class Child_Permutation_traversal{
    public:
      int * left_index; // to boost vector?
      int size;
      int iter;
      Child_Permutation_traversal(int s)
        :size(s),iter(0){
          left_index = new int[s];
        }
      ~Child_Permutation_traversal(){
        delete [] left_index;
      }
  };

  Child_Permutation_traversal ** cpt;
  int size;
  int depth;
  public:
  Permutation_traversal(int s)
  :size(s){
    cpt = new Child_Permutation_traversal * [s + 1];
    int i;
    for(i = 0; i <= s; i++){
      cpt[i] = new Child_Permutation_traversal(s-i);
    }
    for(i = 0; i < s; i++){
      cpt[0]->left_index[i]=i;
    }
    depth = 0;
  }
  ~Permutation_traversal(){
    for(int i=0;i<=size;i++){
      delete cpt[i];
    }
    delete [] cpt;
  }
  bool const empty(){
    return cpt[depth]->size == 0;
  }
  void next(){
    if(cpt[depth]->iter == cpt[depth]->size)
      return ;
    ++(cpt[depth]->iter);
  }
  
  bool const valid(){
    return cpt[depth]->iter != cpt[depth]->size;
  }
  
  int const getvalue(){
    return cpt[depth]->iter != cpt[depth]->size ? cpt[depth]->left_index[cpt[depth]->iter] : -1;
  }

  void select(){
    if(cpt[depth]->iter == cpt[depth]->size)
      return ;
    int newdepth = depth + 1;
    cpt[newdepth]->size = 0;
    cpt[newdepth]->iter = 0;
    for(int it = 0,itlimit=cpt[depth]->size ; it < itlimit ; ++it){
      if(it == cpt[depth]->iter)
        continue;
      cpt[newdepth]->left_index[cpt[newdepth]->size++] = cpt[depth]->left_index[it];
    }
    depth = newdepth;
  }

  void unselect(){
    if(depth > 0)
      --depth;
  }

  int getnum(){
    return 5-cpt[depth]->size;
  }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    pt.select();
    ptdemo(pt);
    pt.unselect();
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}