import java.util.*;

public class MergeSort
{
	public static int sporedbi=0;
	public static int zameni=0;
	public static int[] array;
	public static boolean firstPass = true;
	public static void mergeDevide(String operacija, String nasoka, int array[], int levo, int desno){
		if(levo < desno){
		sporedbi++;
		int sredina = (levo+desno)/2;
		if(operacija.equals("trace")) printArr(array,true,levo,desno,sredina);
		mergeDevide(operacija,nasoka,array,levo,sredina);
		mergeDevide(operacija,nasoka,array,sredina+1,desno);
		mergeMerge(array,levo,sredina,desno,nasoka,operacija);
		}
	}
	public static void mergeMerge(int array[], int levo, int sredina, int desno, String nasoka,String operacija){
		int brojLevo = (sredina - levo) + 1;
		int brojDesno = (desno - sredina);
		int levaPomosna[] = new int[brojLevo];
		int desnaPomosna[] = new int[brojDesno];
		for(int i=0;i<brojLevo;i++)
			levaPomosna[i] = array[levo+i];
		for(int i=0;i<brojDesno;i++)
			desnaPomosna[i] = array[sredina+1+i];
		int dosegaLevo = 0, dosegaDesno = 0,smesteni = levo;
		while(dosegaLevo < brojLevo && dosegaDesno < brojDesno){
			zameni++;
			if(nasoka.equals("up")){
				if(levaPomosna[dosegaLevo] <= desnaPomosna[dosegaDesno]){
					sporedbi++;
					array[smesteni] = levaPomosna[dosegaLevo];
					dosegaLevo++;
				}
				else{
					sporedbi++;
					array[smesteni] = desnaPomosna[dosegaDesno];
					dosegaDesno++;
				}
			}
			else{
				if(levaPomosna[dosegaLevo] >= desnaPomosna[dosegaDesno]){
					sporedbi++;
					array[smesteni] = levaPomosna[dosegaLevo];
					dosegaLevo++;
				}
				else{
					sporedbi++;
					array[smesteni] = desnaPomosna[dosegaDesno];
					dosegaDesno++;
				}
			}
			smesteni++;
		}
		while(dosegaLevo < brojLevo){
			sporedbi++;
			array[smesteni] = levaPomosna[dosegaLevo];
			smesteni++;
			dosegaLevo++;
		}
		while(dosegaDesno < brojDesno){
			sporedbi++;
			array[smesteni] = desnaPomosna[dosegaDesno];
			dosegaDesno++;
			smesteni++;
		}
		for(int i=levo;i<=desno;i++){
			System.out.print(array[i]+"");
		}
		System.out.println();
	}
	public static void printArr(int[] arr,boolean trebaCrta, int levo, int desno, int sredina) {
		for(int i = levo; i <= desno; i++) {
			System.out.print(array[i]+" ");
			if(trebaCrta && i == sredina) {
				System.out.printf("| ");
			}
		}
		System.out.println();
	}

	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String[] s=sc.nextLine().split(" ");
		String operacija=s[0];
		String vidSort=s[1];
		String nasoka=s[2];
		int n=Integer.parseInt(s[3]);
		array=new int[n];
		s=sc.nextLine().split(" ");
		for(int i=0; i<n; i++) array[i]=Integer.parseInt(s[i]);
		mergeDevide(operacija, nasoka, array,0,n-1);
		if(!operacija.equals("trace")){
			System.out.println(zameni+" "+sporedbi+1);
			zameni = 0; sporedbi = 0;
			mergeDevide(operacija, nasoka, array,0,n-1);
			System.out.println(zameni+" "+sporedbi+1);
			zameni = 0; sporedbi = 0;
			if(nasoka.equals("up"))
			nasoka = "down";
			else
			nasoka = "up";
			zameni = 0; sporedbi = 0;
			mergeDevide(operacija, nasoka, array,0,n-1);
			System.out.println(zameni+" "+sporedbi+1);
		}


	}

}