Retrieving Document Paths

Given a nested folder structure represented in JSON format, your task is to generate the full paths for all documents. In the folder structure, each folder may contain either an integer (indicating that it contains that many documents) or another object representing subfolders.

The path is constructed by concatenating folder names separated by forward slashes (/), starting from the root. Documents inside a folder are named as document1, document2, etc. For example, if the folder folder1 under root contains 2 documents, the resulting document paths will be: root/folder1/document1 and root/folder1/document2.

Your solution should recursively traverse the folder structure and output all document paths in lexicographically sorted order. If no documents exist, output nothing.

The mathematical formulation for the number of documents in a folder can be expressed as: \[ \text{paths}(f) = \bigcup_{\text{if } f \text{ is a leaf}} \{ path + "/" + f + "/document" + i \mid 1 \leq i \leq n \} \cup \bigcup_{\text{if } f \text{ is an object}} \{ \text{paths}(child) \} \]

inputFormat

The input consists of a single line containing a valid JSON object representing the folder structure. The JSON object will always have a key root whose value is an object. Each key in the object represents a folder name. A value can either be:

• An integer, representing the number of documents in that folder.
• A JSON object representing subfolders.

You may assume that the JSON is well-formed and does not contain arrays or other data types.

outputFormat

Output all document paths, one per line, in lexicographically sorted order. If there are no documents, output nothing.

{"root":{"folder1":1}}

root/folder1/document1