Flatten a Nested Dictionary

You are given a nested dictionary (in JSON format) where the values can be either strings or other dictionaries. Your task is to flatten the dictionary such that the resulting dictionary has no nested structure. The keys of the flattened dictionary are constructed by concatenating the keys from the original dictionary along the path, separated by a dot.

More formally, if you have a nested dictionary d, then for every key k that maps to a value v:

If v is a string (or any non-dictionary value), then the flattened dictionary will have an entry with the key (if parent is non-empty, then parent + "." + k, otherwise just k) and the corresponding value.

If v is itself a dictionary and is non-empty, then process it recursively. If v is an empty dictionary, ignore it.

The relationship can be expressed using the formula:

\[ flatten(d, parent) = \begin{cases} \{ \} & \text{if } d \text{ is empty or } d[k] \text{ is an empty dictionary} \\ \{ key: value \} & \text{if } d[k] \text{ is a string (or non-dictionary value)} \\ flatten(v, new\_key) & \text{if } d[k] = v \text{ is a non-empty dictionary} \end{cases} \]

Your program should read the nested dictionary from stdin and output the flattened dictionary to stdout in JSON format.

inputFormat

The input is a single JSON string representing a nested dictionary. The dictionary can have multiple levels of nesting. Each key is a string. Each value is either a string or another nested dictionary.

Example Input:

{"key1": "value1", "key2": {"key2_1": "value2_1", "key2_2": {"key2_2_1": "value2_2_1"}}, "key3": "value3"}

outputFormat

The output is a single JSON string representing the flattened dictionary. Keys in the resulting dictionary are the concatenation of the keys encountered along the path, separated by a dot.

Example Output:

{"key1": "value1", "key2.key2_1": "value2_1", "key2.key2_2.key2_2_1": "value2_2_1", "key3": "value3"}

## sample

{"key": "value"}

{"key":"value"}