#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <cmath>

using namespace std;

const int maxn=;

int num1[maxn],num2[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++)

        scanf("%d",&num1[i]);

    for(int i=;i<n;i++)

        scanf("%d",&num2[i]);

    int p,idx;

    for(idx=;num2[idx]<=num2[idx+];idx++);

    p=idx+;

    for(;num2[p]==num1[p] && p<n;p++);

//printf("idx:%d p:%d\n",idx,p);

    if(p==n){

        sort(num2,num2+idx+);

        printf("Insertion Sort\n");

        printf("%d",num2[]);

        for(int i=;i<n;i++){

            printf(" %d",num2[i]);

        }

    }

    else{

        int k;

        bool flag=true;

        for(k=;k<=n;k=(k<<)){

            for(int i=;i<n;i+=k){

                for(int j=i;j<i+k-&&j<n-;j++){

                    if(num2[j]>num2[j+]){

                        flag=false;

                        break;

                    }

                }

                if(!flag)

                    break;

            }

            if(!flag)

                break;

        }

        for(int i=;i<n;i+=k){

            if(i+k-<n){

                sort(num2+i,num2+i+k);

            }

            else

                sort(num2+i,num2+n);

        }

        printf("Merge Sort\n");

        printf("%d",num2[]);

        for(int i=;i<n;i++){

            printf(" %d",num2[i]);

        }

    }

    return ;

}