Merge Two Dictionaries

You are given two dictionaries, each mapping string keys to integer values. Your task is to merge these dictionaries such that if a key appears in both dictionaries, its value in the merged dictionary is the sum of the values from both dictionaries. If a key appears in only one dictionary, its value remains unchanged in the merged dictionary.

All keys in the output should be sorted in lexicographical order.

In mathematical notation, if the first dictionary is \(D_1\) and the second dictionary is \(D_2\), then the merged dictionary \(D\) is defined by: \[ D[k] = \begin{cases} D_1[k] + D_2[k] & \text{if } k \in D_1 \text{ and } k \in D_2, \\ D_1[k] & \text{if } k \in D_1 \text{ and } k \notin D_2, \\ D_2[k] & \text{if } k \notin D_1 \text{ and } k \in D_2. \end{cases} \]

inputFormat

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

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 key and an integer value (separated by a space).
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 string key and an integer value (separated by a space).

outputFormat

Output the merged dictionary to standard output (stdout) as follows:

Print each key-value pair on a separate line with the key and value separated by a space. The keys must be printed in lexicographical order.## sample

3
a 10
b 20
c 30
3
b 5
c 15
d 40

a 10
b 25
c 45
d 40