Merge Two Dictionaries

You are given two dictionaries. Your task is to merge these dictionaries by summing the values of the keys that appear in both dictionaries. If a key exists in only one of the dictionaries, simply include it in the resulting dictionary with its original value.

More formally, if the two input dictionaries are \(D_1\) and \(D_2\), then the resulting dictionary \(D\) should satisfy:

\(\forall key:\; D[key] = \begin{cases} D_1[key] + D_2[key] & \text{if } key \text{ exists in both} \\ D_1[key] & \text{if } key \text{ exists only in } D_1 \\ D_2[key] & \text{if } key \text{ exists only in } D_2 \end{cases}\)

The merged dictionary should be output in JSON format with keys sorted in lexicographical order.

inputFormat

The input is given via standard input (stdin) in the following format:

1. An integer m, representing the number of key-value pairs in the first dictionary.
2. The next m lines each contain a key (a string without spaces) and an integer value separated by a space.
3. An integer n, representing the number of key-value pairs in the second dictionary.
4. The next n lines each contain a key (a string without spaces) and an integer value separated by a space.

You can assume that all keys consist of alphanumeric characters and that the input format is valid.

outputFormat

Output the merged dictionary in JSON format. The keys in the output must be sorted in lexicographical (alphabetical) order. There should be no extra spaces in the output.

2

a 1

b 2

2

b 3

c 4

{"a":1,"b":5,"c":4}