/**
 * @file   1089.cpp
 * @author Shuang Hu <hsmath@ubuntu>
 * @date   Sat Apr 17 04:13:26 2021
 * 
 * @brief  PAT 1089,Insert or Merge
 * 
 * 
 */
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class cmpseq{
private:
    vector<int> origin;
    vector<int> now;
    int nodenum;
    bool isinsert;
    int mergegap;//For mergesort:merge gap
    int knot;//For insertion sort:the position
public:
    cmpseq(int n){
	nodenum=n;
	for(int i=0;i<n;i++){
	    int id;
	    cin>>id;
	    origin.push_back(id);
	}
	for(int i=0;i<n;i++){
	    int id;
	    cin>>id;
	    now.push_back(id);
	}
	isinsert=true;
	mergegap=nodenum;
    }
    void judge();
    void onestep();
};
void cmpseq::judge(){
    int flag=0;//sorted part
    while(now[flag]<now[flag+1]&&flag<nodenum-1){
	flag++;
    }
    flag++;
    knot=flag;
    for(int i=flag;i<nodenum;i++){
	if(origin[i]!=now[i]){//Not insertion!
	    isinsert=false;
	    break;
	}
    }
    if(isinsert==false){
	for(int l=2;l=l*2;l<nodenum){
	    for(int i=1;i<=(nodenum-1)/l;i+=2){
		if(now[i*l-1]>now[i*l]){
		    mergegap=l;
		}
	    }
	    if(mergegap<nodenum){
		break;
	    }
	}
	cout<<"Merge Sort"<<endl;
    }else{
	cout<<"Insertion Sort"<<endl;
    }
}
void cmpseq::onestep(){
    if(isinsert==true){
	for(int i=0;i<knot;i++){
	    if(now[i]>now[knot]){
		int id=now[knot];
		for(int j=knot;j>i;j--){
		    now[j]=now[j-1];
		}
		now[i]=id;
		break;
	    }
	}
    }
    else{//merge_sort
	mergegap*=2;
	int times=nodenum/mergegap;
	for(int i=0;i<times;i++){
	    sort(now.begin()+i*mergegap,now.begin()+(i+1)*mergegap-1);
	}
	if(times==0){
	    sort(now.begin(),now.end());
	}
    }
    cout<<now[0];
    for(int i=1;i<now.size();i++){
	cout<<" "<<now[i];
    }
    cout<<endl;
}
int main(){
    int nodenum;
    cin>>nodenum;
    cmpseq C(nodenum);
    C.judge();
    C.onestep();
}