#include<iostream>
using namespace std;
struct nodoA{int info; nodoA* left,*right; nodoA(int a=0, nodoA*b=0,nodoA*c=0){info=a; left=b; right=c;}};
struct nodo{nodoA* info; nodo* next; nodo(nodoA* a=0, nodo*b=0){info=a; next=b;}};

void stampa_l(nodoA *r)
{
  if(r)
    {
      cout<<r->info<<'(';
      stampa_l(r->left);
      cout<<',';
      stampa_l(r->right);
      cout<<')';
    }
  else
    cout<< '_';
}
int conta_n(nodoA*r)
{
   if(!r) return 0;
     else
    return conta_n(r->left)+conta_n(r->right)+1;
}

nodoA* insert(nodoA*r, int y)
{
  if(!r) return new nodoA(y);

  if(conta_n(r->left)<=conta_n(r->right))
    r->left=insert(r->left,y);
   else
    r->right=insert(r->right,y);
  return r;
}

nodoA* buildtree(nodoA*r, int dim)
{
  if(dim)
   {
    int z;
    cin>>z;
    nodoA*x=insert(r,z);
    return buildtree(x,dim-1);
   }
  return r;
}

void riempi(int*P,int m)
{
  if(m)
    {
      cin>>*P;
      riempi(P+1,m-1);
    }
}
void stampaL(nodo*a)
{
  if(a)
    {
      cout<<a->info->info<<' ';
      stampaL(a->next);
    }
  else
    cout<<endl;
}

nodo*concat(nodo*L1,nodo*L2)
{
    if(!L1)
        return L2;
    if(!L2)
        return L1;
    if(!L1->next)
    {
        L1->next=L2;
            return L1;
    }
    L1->next=concat(L1->next,L2);
    return L1;
}

//PRE=(albero(r)è ben formato, k>0, 1<=n<=k)
nodo* B(nodoA*r, int k, int&n)
{
    if(!r)
        return 0;
    nodo*right,*left=B(r->left,k,n);//chiamo a sinistra
    if(n==1)
    {
        n=k;    //resetto n al valore k iniziale
        nodo*tmp=new nodo(r);   //creo un nuovo nodo che punta a r
        left=concat(left,tmp);  //aggiungo il nuovo nodo alla lista
        right=B(r->right,k,n);  //chiamo a destra
    }
    else
    {
        n=n-1; //decremento n
        right=B(r->right, k,n); //chiamo a destra
    }
    return concat(left,right); //concateno la lista che ho trovato a sinistra con quella di destra
}
/*POST=(restituisce la lista concatenata i cui nodi puntano ai nodi dell’albero ordinati
secondo l’ordine infisso,etale che il primo nodo della lista punti al nodo n-esimo di
albero(r)secondo l’ordine infisso, e i successivi nodi puntano ad un nodo di albero(r)
ogni k nodi sempre secondo l’ordine infisso) && ( n, 1<=n<=k, indica che si devono
attraversare n-1 nodi prima di arrivare a quello che va puntato dal prossimo nodo della lista)*/

main()
{
  int  n,m,k;
  cout<<"start"<<endl;
  cin>> n;
  nodoA*R=buildtree(0,n);
  stampa_l(R);
  cout<<endl;

  cin>> k;
  m=k;
  nodo*a=B(R,k,m); // da fare
  cout<<"lista:"<<endl;
  stampaL(a);
  cout<<"n="<<m<<endl;
  cout<<"end"<<endl;
}