Merge Dictionaries

You are given two dictionaries, each containing key-value pairs where keys are strings and values are integers. Your task is to merge these two dictionaries such that if a key exists in both dictionaries, its values are added together. Otherwise, the key and its associated value are simply added to the merged dictionary. The final merged dictionary must be output in a JSON string format with the keys sorted in lexicographical order.

In mathematical terms, for each key \( k \), if \( k \) exists in both dictionaries with values \( v_1 \) and \( v_2 \), then the resulting value is \( v_1 + v_2 \). Otherwise, the value remains unchanged.

inputFormat

The input is read from standard input (stdin) and follows this format:

1. The first line contains an integer \(N\), the number of key-value pairs in the first dictionary.
2. The next \(N\) lines each contain a string and an integer separated by a space representing the key and its value.
3. The following line contains an integer \(M\), the number of key-value pairs in the second dictionary.
4. The next \(M\) lines each contain a key and an integer value separated by a space.

outputFormat

Output a single line to standard output (stdout) containing the merged dictionary as a JSON string. The keys in the JSON object must be sorted in lexicographical order, and no extra spaces should be included. For example: {"a":4,"b":2,"d":4}.

2
a 1
b 2
2
c 3
d 4

{"a":1,"b":2,"c":3,"d":4}