K Smallest Pairs

You are given two sorted arrays, \(nums1\) and \(nums2\), and an integer \(k\). Your task is to find the \(k\) pairs \((u, v)\), where \(u\) is chosen from \(nums1\) and \(v\) is chosen from \(nums2\), such that the sum \(u+v\) is as small as possible. The answer pairs should be returned in ascending order of their sums.

Note:

• If there are fewer than \(k\) possible pairs, return all possible pairs.
• The arrays are assumed to be sorted in non-decreasing order.

The sum of a pair \((u, v)\) is represented as \(u+v\). Use an efficient algorithm such as a min-heap to obtain the required pairs.

inputFormat

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

1. An integer \(n\) representing the number of elements in the first array.
2. \(n\) space-separated integers representing the elements of the first array.
3. An integer \(m\) representing the number of elements in the second array.
4. \(m\) space-separated integers representing the elements of the second array.
5. An integer \(k\) representing the number of pairs to find.

outputFormat

Output the \(k\) pairs to stdout, one pair per line. Each line should contain two integers separated by a single space. If no pairs can be formed or if \(k = 0\), output nothing.

## sample

3
1 7 11
3
2 4 6
3

1 2
1 4
1 6

</p>