PROGRAMMING:Insert sort or merge sort
According to the definition of Wikipedia:
**Insert sort * * is an iterative algorithm, which obtains the input data one by one and produces an orderly output sequence step by step. In each iteration, the algorithm takes an element from the input sequence and inserts it into the correct position in the ordered sequence. So iterate until all the elements are in order.
**Merge sort * * iterates as follows: first, the original sequence is regarded as n ordered subsequences with only one element, and then each iteration merges two adjacent ordered subsequences until only one ordered sequence is left.
Now, given the original sequence and the intermediate sequence generated by a sort algorithm, please judge which sort algorithm this algorithm is?
###Input format:
Enter the positive integer n ($$$Le $$100) in the first line; The next line gives n integers of the original sequence; The last line gives the intermediate sequence generated by a sort algorithm. Here, we assume that the target sequence is ascending. Numbers are separated by spaces.
###Output format:
First, in line 1, output 'insertion sort' for insertion sort, or 'merge sort' for merge sort; Then, in the second line, the result sequence of another iteration with the sorting algorithm is output. The questions ensure that the results of each group are unique. The numbers should be separated by spaces, and there should be no extra spaces at the beginning and end of the line.
###Input sample 1:
```in
ten
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
```
###Output sample 1:
```out
Insertion Sort
1 2 3 5 7 8 9 4 6 0
```
###Input example 2:
```in
ten
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
```
###Output example 2:
```out
Merge Sort
1 2 3 8 4 5 7 9 0 6
```
answer：If there is no answer, please comment
**Insert sort * * is an iterative algorithm, which obtains the input data one by one and produces an orderly output sequence step by step. In each iteration, the algorithm takes an element from the input sequence and inserts it into the correct position in the ordered sequence. So iterate until all the elements are in order.
**Merge sort * * iterates as follows: first, the original sequence is regarded as n ordered subsequences with only one element, and then each iteration merges two adjacent ordered subsequences until only one ordered sequence is left.
Now, given the original sequence and the intermediate sequence generated by a sort algorithm, please judge which sort algorithm this algorithm is?
###Input format:
Enter the positive integer n ($$$Le $$100) in the first line; The next line gives n integers of the original sequence; The last line gives the intermediate sequence generated by a sort algorithm. Here, we assume that the target sequence is ascending. Numbers are separated by spaces.
###Output format:
First, in line 1, output 'insertion sort' for insertion sort, or 'merge sort' for merge sort; Then, in the second line, the result sequence of another iteration with the sorting algorithm is output. The questions ensure that the results of each group are unique. The numbers should be separated by spaces, and there should be no extra spaces at the beginning and end of the line.
###Input sample 1:
```in
ten
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
```
###Output sample 1:
```out
Insertion Sort
1 2 3 5 7 8 9 4 6 0
```
###Input example 2:
```in
ten
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
```
###Output example 2:
```out
Merge Sort
1 2 3 8 4 5 7 9 0 6
```
answer：If there is no answer, please comment