Nested Object Search

Given a JSON object that may contain nested objects, your task is to search for a specific key recursively and print its corresponding value. If the key is found directly at any level of nesting, return its value immediately. Otherwise, continue searching in any nested objects. If the key does not exist in the entire structure, output None.

More formally, let \(O\) be a JSON object and \(k\) be the key to search. The recursive definition is as follows: \[ \text{search}(O, k) = \begin{cases} O[k] &\text{if } k \in O,\\ \text{search}(v, k) &\text{if } v \text{ is an object and } k \text{ is in } v,\\ \text{None} &\text{if } k \text{ is not found in } O \text{ or any nested object.} \end{cases} \]

inputFormat

The input consists of two lines provided via stdin:

• The first line is a valid JSON string representing a nested object. The JSON object will include keys and string values, or nested objects.
• The second line is a string representing the key to search for.

outputFormat

Print the value associated with the given key if it is found; otherwise, print None. The output should be sent to stdout.

{"level1": {"level2": {"level3": "found me"}, "anotherLevel2": {"anotherLevel3": "hello"}}}
level3

found me