#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int a[N], b[N], c[N], tmp[N];
bool is1 = false;
int n;
bool check(){
    for(int i = 0;i < n; i++) 
        if(b[i] != c[i]) return false;
    return true;
}

void dfs1(){
    bool got = false;
    for(int i = 0;i < n; i++){
        int t = i - 1;
        while(t >= 0 && b[t] > b[i]) t --;
        int x = b[i];
        for(int k = i; k > t + 1; k --) b[k] = b[k - 1];
        b[t + 1] = x;

        if(got){
            for(int i = 0;i < n - 1; i ++) cout << b[i] << " ";
            cout << b[n - 1];
            return;
        }
        else if(check()){
            cout << "Insertion Sort" << endl;
            is1 = true;
            got = true;
        }
    }
}


/*归并排序的非递归写法*/

void dfs2(){
    int step = 1;//step表示每个序列的
    bool got = false;
    while(n / step){ // n / step 表示目前有多少个序列，每个序列长度是step
        for(int l = 0; l < n; l += 2*step){  //for循环每一组，每一组有两个序列
            //l表示这两个子序列中第一个序列
            //的开头位置，l + step表示第二个
            //子序列的开头位置
            int p1 = l, p2 = l + step, k = 0;
            //第一个子序列的范围[l,l+step)
            //第二个序列的范围[l+step,l+step+step)
            while(p1 < l + step && p2 < l + 2*step && p1 < n && p2 < n){
                if(b[p1] < b[p2]) tmp[k ++] = b[p1 ++];
                else tmp[k ++] = b[p2 ++];
            }
            while(p1 < n && p1 < l + step) tmp[k ++] = b[p1 ++];
            while(p2 < n && p2 < l + 2*step) tmp[k ++] = b[p2 ++];
            for(int i = l, k = 0; i < n && i < l + 2*step; i ++, k++) b[i] = tmp[k];

        }
        if(got){
                for(int i = 0; i < n - 1; i++) cout << b[i] << " ";
                cout << b[n - 1];
                return;
            }
            else if(check()){
                got = true;
                cout << "Merge Sort" << endl;
            }
        step *= 2;
    }

}

int main(){
    scanf("%d", &n);
    for(int i = 0;i < n;i ++) scanf("%d", &a[i]);
    for(int i = 0;i < n; i++ ) scanf("%d", &c[i]);
    memcpy(b, a, sizeof(int) * n);
    dfs1();
    if(!is1){
        memcpy(b, a, sizeof(int) * n);
        dfs2();
    }
    return 0;
}