You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ... with the smallest sums.

Example 1:

Input:
1 7 11
2 4 6
3
Output:
1 2
1 4
1 6

Example 2:

Input:
1 1 2
1 2 3
2
Output:
1 1
1 1

Constraints:

• 1 ≤ nums1.length, nums2.length ≤ 10⁵
• 1 ≤ k ≤ 10⁴

Input format: First line: nums1. Second line: nums2. Third line: k.

Output format: k pairs, one per line (ui vi).