Merge and Sort Two Dictionaries

You are given two dictionaries. The task is to merge them into one dictionary. If a key exists in both dictionaries, sum the values. After merging, sort the dictionary based on the following rules:

• Sort by values in descending order.
• If two keys have the same value, sort them in alphabetical ascending order.

For example, merging {'a': 1, 'b': 2} and {'c': 3, 'd': 4} should yield {'d': 4, 'c': 3, 'b': 2, 'a': 1} and merging {'a': 1, 'b': 2} with {'b': 3, 'c': 1} results in {'b': 5, 'a': 1, 'c': 1} since when values are equal, keys are arranged alphabetically.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers N and M separated by a space, representing the number of elements in the first and second dictionaries respectively.
2. The next N lines each contain a key (a string without spaces) and an integer value, separated by a space, representing an entry of the first dictionary.
3. The following M lines each contain a key and an integer value, separated by a space, representing an entry of the second dictionary.

outputFormat

Output the merged dictionary to stdout in sorted order. Each line of output should contain a key and its corresponding value separated by a space.

2 2
a 1
b 2
c 3
d 4

d 4
c 3
b 2
a 1