Design a simple file directory system that supports two main operations:

• addPath(location, val): Adds a new directory path with an associated integer value if possible and returns true. Returns false if the path already exists or if its parent directory does not exist.
• fetch(location): Returns the value assigned to the given path, or -1 if the path does not exist.

Each path string consists of one or more segments starting with a slash (/) followed by lowercase English letters. For example, /home and /home/user are valid paths, but empty strings or just / are invalid.

Implement these two functions accordingly.

Examples

Input:
["DirectorySystem","addPath","fetch"]
[[],["/x",5],["/x"]]
Output:
[null,true,5]
Explanation:
DirectorySystem dirSys = new DirectorySystem();

dirSys.addPath("/x", 5); // returns true
dirSys.fetch("/x"); // returns 5

Input:
["DirectorySystem","addPath","addPath","fetch","addPath","fetch"]
[[],["/dir",3],["/dir/subdir",8],["/dir/subdir"],["/a/b",2],["/a"]]
Output:
[null,true,true,8,false,-1]
Explanation:
DirectorySystem dirSys = new DirectorySystem();

dirSys.addPath("/dir", 3); // returns true
dirSys.addPath("/dir/subdir", 8); // returns true
dirSys.fetch("/dir/subdir"); // returns 8
dirSys.addPath("/a/b", 2); // returns false because parent "/a" does not exist
dirSys.fetch("/a"); // returns -1 because path does not exist

Constraints

• There will be at most 12,000 calls made to both functions combined.
• Each path has length between 3 and 120 characters.
• Values assigned to paths are integers between 1 and 10⁸.