Merge K timestamped lists with timestamp coalescing

You are given k sorted lists (or linked lists) of records. Each record has:

• timestamp (integer)
• values (an array of integers sorted in non-decreasing order)

Each individual list is sorted by timestamp in non-decreasing order.

Your task is to merge the k lists into one sorted list by timestamp, with the following special rule:

• If multiple input records (possibly from different lists) have the same timestamp , you must coalesce them into a single output record with that timestamp.
• The values array of the coalesced record is the sorted merge of all values arrays from records with that timestamp.

Return the merged list of records sorted by timestamp.

Input

• lists : an array of length k , where each element is a list of records (timestamp, values) sorted by timestamp .

Output

• A single list of records (timestamp, values) sorted by timestamp , where each timestamp appears at most once.

Constraints (you may assume)

• 0 <= k <= 10^4
• Total number of records across all lists: N (up to ~10^5)
• Total number of integers across all values arrays: M (up to ~10^5)
• Timestamps fit in 32-bit signed integer.

Example

Input:

• L1: (1,[1,4]) -> (3,[2])
• L2: (1,[0,5]) -> (2,[7])
• L3: (3,[3,3])

Output:

• (1,[0,1,4,5]) -> (2,[7]) -> (3,[2,3,3])

(Notice timestamps 1 and 3 are merged first across lists, and their values arrays are merged into one sorted array.)