Merge

Interview

Time limit2sMemory limit512 MB

Summary

Merge two sorted sequences into one sorted sequence using the given tie-breaking rule, which takes from A when the front elements are equal.

Level: Easy2 of 10
Topics: Two pointers, Implementation, Array, Sorting
Solved: No attempts yet

Problem

You are given a sequence of positive integers A=(A1, A2, ..., AN) of length N and a sequence of positive integers B=(B1, B2, ..., BM) of length M. Both sequences are non-decreasing, that is, A1 ≦ A2 ≦ … ≦ AN and B1 ≦ B2 ≦ … ≦ BM.

The following algorithm generates a sequence of positive integers C=(C1, C2, ..., CN+M) of length N+M from these sequences.

Initially C is empty.
If both A and B are empty, stop.
If exactly one of A and B is empty, let t be the non-empty sequence. If both are non-empty, let t be the sequence whose first element is smaller. If the first elements of A and B are equal, let t be A.
Append the first element of t to the end of C.
Remove the first element of t.
Go back to step 2.

Given non-decreasing sequences of positive integers A and B, write a program that outputs the sequence of positive integers C generated by this algorithm.

Input

Input is given from standard input in the following format.

N M
A1 A2 … AN
B1 B2 … BM

Output

Print N + M lines to standard output.

On the k-th line (1 ≦ k ≦ N + M), print Ck.

Constraints

1 ≦ N ≦ 500.
1 ≦ M ≦ 500.
1 ≦ A1 ≦ A2 ≦ … ≦ AN ≦ 2000.
1 ≦ B1 ≦ B2 ≦ … ≦ BM ≦ 2000.

Examples2

Example 1
Input
```
2 1
1 2
2
```
Expected output
```
1
2
2
```

Example 2

Input

3 8
1 3 8
3 3 4 5 6 7 8 9

Expected output