Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge them into one new sorted linked list.

Formally, given two linked lists \(L_1\) and \(L_2\) sorted in non-decreasing order, you need to produce a new list \(L_3\) that contains all the nodes of \(L_1\) and \(L_2\) in sorted order. That is, if the input lists are:

• \(L_1 = [a_1, a_2, \dots, a_n]\)
• \(L_2 = [b_1, b_2, \dots, b_m]\)

Then the resulting list \(L_3\) should be the sorted merge of both lists.

inputFormat

The input is provided via standard input (stdin) with exactly two lines. Each line represents a sorted linked list. The numbers in each line are separated by spaces. An empty line represents an empty list.

outputFormat

Print the merged sorted linked list to standard output (stdout) in a single line. Numbers should be separated by a single space. If the merged list is empty, output nothing.## sample

1 2 4
1 3 4

1 1 2 3 4 4