#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

inline void swap(int& a, int& b) { a ^= b ^= a ^= b; }

void HeapAdjust(int* heap, int idx, int length) {
	for (int i = 2 * idx + 1;i < length;i = 2 * idx + 1) {
		if (i + 1 < length&&heap[i] < heap[i + 1])i++;
		if (heap[idx] > heap[i])break;
		swap(heap[idx], heap[i]);
		idx = i;
	}
}

int main(int argc, const char* argv[]) {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;

	int ini[100], mid[100];
	for (int i = 0;i < N;i++)cin >> ini[i];
	for (int i = 0;i < N;i++)cin >> mid[i];
	int same = N - 1;
	while (ini[same] == mid[same])same--;
	bool isInsert = true;
	for (int i = 0;i<same;i++)
		if (mid[i] > mid[i + 1]) {
			isInsert = false;
			break;
		}

	if (isInsert) {
		cout << "Insertion sort\n";
		int target = mid[++same];
		int i = 0;
		while (mid[i] < target)i++;
		while (same != i)swap(mid[same], mid[same - 1]), same--;
	}
	else {
		cout << "Heap sort\n";
		int length = N - 1;
		while (mid[length] > mid[0])length--;
		swap(mid[length], mid[0]);
		HeapAdjust(mid, 0, length);
	}
	for (int i = 0;i < N-1;i++)cout << mid[i]<<" ";
	cout << mid[N - 1];

	return 0;
}