You are given two integer arrays arr1[] and arr2[] sorted in ascending order and an integer k. Suppose a pair (a, b) which consists of one element from the first array and one element from the second array. Write a program to find the k pairs (a1, b1), (a2, b2)...(ak, bk) with the smallest sums.

Example 1

Input: arr1[] = [2,8,12], arr2[] = [4,6,8], k = 3
Output: [[2,4],[2,6],[2,8]] 
Explanation: The first 3 pairs are returned from the sequence: [2,4],[2,6],[2,8],[8,4],[8,6],[12,8],[8,8],[12,6],[12,8]

Example 2

Input: arr1[] = [3,3,4], arr2[] = [3,4,5], k = 2
Output: [3,3],[3,3]
Explanation: The first 2 pairs are returned from the sequence: [3,3],[3,3],[3,5],[4,3],[3,4],[4,4],[3,5],[3,5],[4,5]

Example 3

Input: arr1[] = [5,6], arr2[] = [7], k = 3
Output: [5,7],[6,7]
Explanation: All possible pairs are returned from the sequence: [5,7],[6,7]