Merge Sorted Dictionaries

You are given two dictionaries (or maps) where the keys are integers and the values are sorted lists of integers. Your task is to merge these dictionaries into a single dictionary. For each key that appears in either dictionary, the corresponding value in the merged dictionary should be the sorted merge of the two lists associated with that key.

Formally, let\(D_1\) and \(D_2\) be two dictionaries. Define \(D\) as the merged dictionary such that

[ D[k] = \text{sort}(D_1[k] \cup D_2[k]) ]

for every key \(k\) in \(D_1\cup D_2\). If a key is not present in one of the dictionaries, treat its corresponding list as empty.

The input and output are provided in a custom format described below.

inputFormat

The first part of the input describes the first dictionary followed by the second dictionary.

Input format:

N
key1 L1 a1 a2 ... aL1
key2 L2 b1 b2 ... bL2
... (N lines in total)
M
key1 L1 c1 c2 ... cL1
key2 L2 d1 d2 ... dL2
... (M lines in total)

Where:

• N is the number of entries in the first dictionary.
• Each of the next N lines contains an integer key, followed by an integer representing the length of the list, and then the list elements in sorted order.
• M is the number of entries in the second dictionary, followed by M lines in similar format.

outputFormat

The output is the merged dictionary in the following format:

K
key1 L1 e1 e2 ... eL1
key2 L2 f1 f2 ... fL2
... (K lines in total)

Where:

• K is the number of keys in the merged dictionary.
• Each subsequent line contains a key (in increasing order), followed by the number of elements in the merged list, and then the sorted list elements.

## sample

2
1 3 2 4 6
3 3 1 5 9
2
1 3 1 3 7
2 3 2 3 5

3
1 6 1 2 3 4 6 7
2 3 2 3 5
3 3 1 5 9

</p>