import heapq # 引入最小堆
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:        
        heap = []
        for i in range(len(nums2)): 
            a = (0,i) 
            cur_s = nums1[0] + nums2[i]            
            heapq.heappush(heap, (cur_s,a))
        res = []
        cnt = 0
        # 遍历
        while(len(heap) and cnt < k):
            head = heapq.heappop(heap)
            cur_s,a = head
            i,j = a
            print(i,j)
            if i+1 < len(nums1):
                heapq.heappush(heap,(nums1[i+1]+nums2[j],(i+1,j)))            
            cnt += 1
            res.append([nums1[i],nums2[j]])
        return