Directories required for creating a folder tree Say that you have this folder structure on your coumputer:

/a


And you want to have these folders:

/a/b
/a/c
/b/b


You would need to create four directories, using mkdir for example:

mkdir /a/b
mkdir /a/c
mkdir /b
mkdir /b/b


Write a program that, given existing and required directory structures, will output the directories that need to be created.

Input

First line has two numbers: n, number of existing directories, and m, number of required directories
Next n lines has the list of existing directories
Next m lines has the list of required directories

Example:

1 3
/a
/a/b
/a/c
/b/b


Output

Directories you need to create

Example: 

/a/b
/a/c
/b
/b/b
Python
 
In Python, you would just use os.makedirs(). See the docs at the bottom of this post
import sys

num_existing, num_required = map(int, next(sys.stdin).split())

sep = &quot;/&quot;
directory = {}

for i,path in enumerate(s.rstrip(&quot;\n&quot;) for s in sys.stdin):
    d = directory    
    base = &quot;&quot;
    for p in path.split(sep)[1:]:
        base += sep+p
        if p not in d:
            if i &gt;= num_existing:
                print base
            d[p]={}
        d = d[p]

Python docs for os.makedirs()
&gt;&gt;&gt; import os
&gt;&gt;&gt; help(os.makedirs)

Help on function makedirs in module os:

makedirs(name, mode=511)
    makedirs(path [, mode=0777])
    
    Super-mkdir; create a leaf directory and all intermediate ones.
    Works like mkdir, except that any intermediate path segment (not
    just the rightmost) will be created if it does not exist.  This is
    recursive.