Merge dictionaries A and B. Sum values for keys present in both and preserve values for keys present in only one. Preserve key order from A, followed by new keys from B.</p>

Input

Line 1 contains n; line 2 contains n space-separated key:value pairs of A. Line 3 contains m; line 4 contains m pairs of B (1 ≤ n,m ≤ 300000). Keys are distinct within each dictionary.

Output

Print C as a Python-style dictionary literal: {'key': value, ...}, using single quotes and the required key order.

Examples

Input #1

3
apple:3 banana:5 orange:2
2
banana:4 kiwi:10

Output #1

{'apple': 3, 'banana': 9, 'orange': 2, 'kiwi': 10}

Explanation #1: banana occurs in both dictionaries, so its merged value is 5 + 4 = 9. kiwi is appended after all keys from A.

Input #2

1
x:-3
1
x:3

Output #2

{'x': 0}

Explanation #2: The shared key x has merged value -3 + 3 = 0; keys with value zero remain in the dictionary.