//当检测到数列与所给数列相同之后，要在下一次发生insertion时，也就是当数列发生了改变时，才输出#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;bool compare(vector<int> a, vector<int> b) {    for (int i = 0; i != n; ++i) {        if (a[i] != b[i]) {            return false;        }    }    return true;}void print(vector<int> a) {    for (int i = 0; i != n - 1; ++i) {        printf("%d ", a[i]);    }    printf("%d\n", a[n - 1]);}bool doInsert(vector<int> in, vector<int> re) {    vector<int>::iterator it1 = in.begin();    vector<int>::iterator it2 = in.begin();    bool find = false;    for (; it2 != in.end();) {        if (!find && compare(in, re)) {            printf("Insertion Sort\n");            find = true;        }        advance(it2, 1);        sort(it1, it2);        if (find && !compare(in, re)) {            print(in);            return true;        }    }    return false;}void doMerge(vector<int> me, vector<int> re) {    int k = (int)(log(n*1.0) / log(2.0));    bool find = false;    for (int i = 0, step = 2; i != k; ++i, step *= 2) {        if (!find && compare(me, re)) {            printf("Merge Sort\n");            find = true;        }        vector<int>::iterator it1 = me.begin();        vector<int>::iterator it2;        for (int j = 0; j != n / step; ++j) {            if (j != 0) {                advance(it1, step);            }            it2 = it1;            advance(it2, step);            sort(it1, it2);        }        if (it2 != me.end()) {            sort(it2, me.end());        }        if (find && !compare(me, re)) {            print(me);            return;        }    }    sort(me.begin(), me.end());    print(me);}int main() {    scanf("%d", &n);    vector<int> in, me, re;    int num;    for (int i = 0; i != n; ++i) {        scanf("%d", &num);        in.push_back(num);        me.push_back(num);    }    for (int i = 0; i != n; ++i) {        scanf("%d", &num);        re.push_back(num);    }    if (doInsert(in, re)) {        return 0;    }    doMerge(me, re);    return 0;}