Secrets of Legendary Treasure
InterviewTime limit1sMemory limit512 MB
Two ascending sequences of distinct numbers from 1 to n+m are given with some entries erased to 0; restore any valid pair.
- Level
Medium5 of 10
- Topics
- Greedy, Array, Sorting, Implementation
- Solved
- No attempts yet
Problem
At last, you have found the document with two integer sequences, the final keys to unlocking the secret of the legendary treasure! The ink on the document, however, has faded so much that some of the numbers in the sequences are too faint to read. Fortunately, you have heard of a legend about the properties of the key sequences: (1) the numbers in the two sequences are all different and lie between 1 and the sum of the lengths of the two sequences, and (2) both sequences are arranged in ascending order.
Restore the original sequences from the readable numbers and the legend.
Input
The input consists of a single test case of the following format.
n m
a1 . . . an
b1 . . . bm
The first line contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 100). They are the lengths of the two sequences A and B, respectively. The second line describes the sequence A. Each ai is either 0, meaning that the i-th element of A is unreadable, or a positive integer 1 ≤ ai ≤ n + m, meaning that the element reads ai. The third line describes the sequence B in the same fashion.
Output
Print a pair of restored sequences A and B on two lines. The sequences must be consistent with the input and with the legendary properties of the sequences.
Print the elements of sequence A on the first line, separated by a space character. Then print the elements of sequence B on the second line, in the same manner.
If there are multiple possibilities, print any one of such pairs. At least one sequence pair consistent with the input and conforming to the legend is guaranteed to exist.
Hint
The second sample input has other acceptable outputs, such as the one with the positions of 6 and 7 exchanged.