In-Place Merging of Two Sorted Arrays

You are given two sorted arrays \(A\) and \(B\) of lengths \(n\) and \(m\) respectively. Your task is to merge these arrays in-place without using extra space such that after merging, the first \(n\) smallest elements are stored in \(A\) and the remaining \(m\) elements are stored in \(B\).

Note: Although the typical in-place merge doesn’t allow extra space, you are allowed to temporarily extend array \(A\) to facilitate the merging process. After merging, split the combined array back into \(A\) and \(B\) of their original sizes.

Input Constraints:

• \(1 \le n, m \le 10^5\)
• All elements in each array are in non-decreasing order.

Example:

Input:
5
1 3 5 7 9
4
2 4 6 8
Output:
1 2 3 4 5
6 7 8 9

</p>

inputFormat

The input is read from stdin and consists of four lines:

1. An integer \(n\), the number of elements in array \(A\).
2. \(n\) space-separated integers representing the elements of array \(A\) in sorted order.
3. An integer \(m\), the number of elements in array \(B\).
4. \(m\) space-separated integers representing the elements of array \(B\) in sorted order.

outputFormat

The output is written to stdout in two lines:

1. The first line contains the \(n\) space-separated integers representing the modified array \(A\) (the smallest \(n\) elements after merging).
2. The second line contains the \(m\) space-separated integers representing the modified array \(B\) (the remaining \(m\) elements after merging).

## sample

5
1 3 5 7 9
4
2 4 6 8

1 2 3 4 5
6 7 8 9

</p>