Sort Nested Dictionaries by a Specified Key

You are given a list of nested dictionaries (JSON objects) and a key. Your task is to sort the list by the value associated with the given key. The key may appear at any depth within the nested dictionaries. If a dictionary does not contain the key anywhere in its hierarchy, it should be placed at the end in its original order.

The sorting criterion is as follows:

• For dictionaries that contain the key, sort them in increasing order of the associated value (values can be integers or floats).
• Dictionaries that do not contain the key should remain in their original order and appear after all dictionaries that contain the key.

Note: The value comparison uses the natural ordering of numbers. You may assume that if the key is present, its value is either an integer or a float.

It is guaranteed that the input list is a valid JSON array and the dictionaries may be arbitrarily nested.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a string representing the key to sort by.
2. The second line is a JSON array of dictionaries. Each dictionary may contain nested dictionaries.

For example:

id
[{"level1": {"level2": {"id": 3, "value": "C"}}}, {"level1": {"level2": {"id": 1, "value": "A"}}}, {"level1": {"level2": {"id": 2, "value": "B"}}}, {"level1": {"info": {"name": "D"}}}]

outputFormat

The output, written to stdout, is the JSON array of dictionaries after sorting. The output should be a valid JSON string.

For the above input example, the correct output is:

[{"level1": {"level2": {"id": 1, "value": "A"}}}, {"level1": {"level2": {"id": 2, "value": "B"}}}, {"level1": {"level2": {"id": 3, "value": "C"}}}, {"level1": {"info": {"name": "D"}}}]

## sample

id
[{"level1": {"level2": {"id": 3, "value": "C"}}}, {"level1": {"level2": {"id": 1, "value": "A"}}}, {"level1": {"level2": {"id": 2, "value": "B"}}}, {"level1": {"info": {"name": "D"}}}]

[{"level1": {"level2": {"id": 1, "value": "A"}}}, {"level1": {"level2": {"id": 2, "value": "B"}}}, {"level1": {"level2": {"id": 3, "value": "C"}}}, {"level1": {"info": {"name": "D"}}}]