Flatten a Nested Dictionary

Given a nested dictionary, your task is to flatten it such that all keys from different depths are combined into a single key by concatenating them with an underscore _ as a separator.

More formally, if you have a nested dictionary \( D \) and for a nested key \( k_1, k_2, \ldots, k_n \) with value \( v \), the flattened dictionary should contain an entry \( {k_1\_k_2\_\cdots\_k_n: v} \).

Example:

If the input is \( {"a": 1, "b": {"c": 2, "d": {"e": 3, "f": 4}}} \), then the output should be \( {"a": 1, "b_c": 2, "b_d_e": 3, "b_d_f": 4} \).

inputFormat

A single line containing a JSON object representing a nested dictionary. The keys are strings and the values are either integers or nested dictionaries.

outputFormat

Output the flattened dictionary as a JSON object in a single line. Use an underscore '_' to join keys from nested dictionaries.## sample

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

{"a":1,"b_c":2,"b_d_e":3,"b_d_f":4}