Description:


跳蚤OS 是跳蚤国自主研发的功能强大的操作系统。
跳蚤OS的文件系统与普通的文件系统类似,是个文件夹套文件夹的结构。文件系统根目录称为“/”。我们可以用文件路径来表明文件所在的位置,比如“/flea/uoj”表示根目录下的flea文件夹下的uoj文件。
跳蚤OS的文件系统中。快捷方式是一种特殊的文件夹,点开该快捷方式相当于打开该快捷方式指向的文件夹。
比如,如果有一个快捷方式 “/etc/abc”,该快捷方式指向 “/flea/def”这个文件夹,那么一旦访问“/etc/abc”就相当于访问“/flea/def”。
这一天,跳蚤国王正在使用跳蚤OS。初始时文件系统为空,只有根目录。他每次会进行如下操作:
首先,随便写出两个文件路径 s 和 t。
接着,如果位置 t 处不存在文件,则在该处创建一个空文件夹。
最后,跳蚤国王保证 s 这个位置没有文件,于是在 s 处创建一个快捷方式指向 t。如果 t 是个快捷方式,那么 s 将指向 t 所指向的文件夹。
上文所说的“创建”在父级目录不存在的时候要一并创建其父级目录。比如,假设文件系统里只有 “/v” 这个文件夹,那么现在我创建 “/v/flea/king/qaq/v/flea/king/qaq” 就会在文件系统中新增三个文件夹:“/v/flea”, “/v/flea/king”, “/v/flea/king/qaq”。
跳蚤国王进行了 n 次这样的操作后,开始不断问他的助手伏特:现在我如果在 p 这个路径处创建一个文件夹(如果已存在则不创建),那么这个文件夹的真实路径是什么?
于是伏特只好向你求助了,请你帮一帮他吧!请参照样例来更清晰地理解题意。

Input:


第一行两个正整数n,m,表示跳蚤国王进行了n个操作,提了m个问题。
接下来n行每行两个用空格隔开的字符串s,t,表示跳蚤国王的一次操作。
接下来 m 行每行一个字符串 p 表示跳蚤国王的一个询问。
保证所有的 s,t,p 都是合法的文件路径。即,文件夹名一定是由小写英文字母组成的非空字符串,路径名一定形如“/xxx/xxx/xxx/.../xxx”这样子。保证当路径不为根目录“/”时,路径不以“/”结尾。

Output:


对于跳蚤国王的每个询问输出真实路径。

Sample Input:


Sample Output:


Explanation:


创建的快捷方式分别为:
/root→/
/duliu→/picks
/vfk→/vfleaking
orz/orz/orz→/picks
/otl→/picks/duliu
/vfleaking/sb→/vfleaking

题解:


这是一道Trie的好题,比较难想。
直接构造Trie,增加一个go数组,表示在该路径下快捷方式指向,然后就可以了。
具体见代码: