Merge Chat Messages

Problem: Merge Chat Messages You are implementing a chat inbox that merges messages from multiple chats/threads into a single global timeline. You are given k chat conversations. Messages inside each conversation are already sorted by timestamp in ascending order. Output all messages in globally merged timestamp order. Each message contains: message_id: a unique message ID, string timestamp: an integer timestamp sender: sender name, string text: message body, string without spaces in this problem Merge rules: Sort by timestamp ascending. If two messages have the same timestamp, output the message from the smaller chat index first. If multiple messages in the same chat have the same timestamp, preserve their original order. Output the message_id of each merged message, one per line. Input Format k chat_id_0 n_0 message_id timestamp sender text ... chat_id_1 n_1 message_id timestamp sender text ... Output Format Print one message_id per line in the merged global order. Constraints 0 <= k <= 10^5 Total number of messages N <= 2 * 10^5 0 <= timestamp <= 10^18 Messages inside each chat are sorted by non-decreasing timestamp. Example Input: 3 chatA 3 a1 1 u1 hi a2 4 u2 ok a3 7 u1 bye chatB 2 b1 2 u3 yo b2 4 u3 lol chatC 1 c1 3 u4 hey Output: a1 b1 c1 a2 b2 a3 Example Input 3 chatA 3 a1 1 u1 hi a2 4 u2 ok a3 7 u1 bye chatB 2 b1 2 u3 yo b2 4 u3 lol chatC 1 c1 3 u4 hey Output a1 b1 c1 a2 b2 a3