跳蚤OS 是跳蚤国自主研发的功能强大的操作系统。

跳蚤OS的文件系统与普通的文件系统类似，是个文件夹套文件夹的结构。文件系统根目录称为“$\texttt{/}$”。我们可以用文件路径来表明文件所在的位置，比如“$\texttt{/flea/uoj}$”表示根目录下的$\texttt{flea}$文件夹下的$\texttt{uoj}$文件。

跳蚤OS的文件系统中。快捷方式是一种特殊的文件夹，点开该快捷方式相当于打开该快捷方式指向的文件夹。

比如，如果有一个快捷方式 “$\texttt{/etc/abc}$”，该快捷方式指向 “$\texttt{/flea/def}$”这个文件夹，那么一旦访问“$\texttt{/etc/abc}$”就相当于访问“$\texttt{/flea/def}$”。

这一天，跳蚤国王正在使用跳蚤OS。初始时文件系统为空，只有根目录。他每次会进行如下操作：

1. 首先，随便写出两个文件路径 $s$ 和 $t$。
2. 接着，如果位置 $t$ 处不存在文件，则在该处创建一个空文件夹。
3. 最后，跳蚤国王保证 $s$ 这个位置没有文件，于是在 $s$ 处创建一个快捷方式指向 $t$。如果 $t$ 是个快捷方式，那么 $s$ 将指向 $t$ 所指向的文件夹。

上文所说的“创建”在父级目录不存在的时候要一并创建其父级目录。比如，假设文件系统里只有 “$\texttt{/v}$” 这个文件夹，那么现在我创建 “$\texttt{/v/flea/king/qaq}$” 就会在文件系统中新增三个文件夹：“$\texttt{/v/flea}$”, “$\texttt{/v/flea/king}$”, “$\texttt{/v/flea/king/qaq}$”。

跳蚤国王进行了 $n$ 次这样的操作后，开始不断问他的助手伏特：现在我如果在 $p$ 这个路径处创建一个文件夹（如果已存在则不创建），那么这个文件夹的真实路径是什么？

于是伏特只好向你求助了，请你帮一帮他吧！请参照样例来更清晰地理解题意。

输入格式

第一行两个正整数$n, m$，表示跳蚤国王进行了$n$个操作，提了$m$个问题。

接下来$n$行每行两个用空格隔开的字符串$s, t$，表示跳蚤国王的一次操作。

接下来 $m$ 行每行一个字符串 $p$ 表示跳蚤国王的一个询问。

保证所有的 $s, t, p$ 都是合法的文件路径。即，文件夹名一定是由小写英文字母组成的非空字符串，路径名一定形如“$\texttt{/xxx/xxx/xxx/.../xxx}$”这样子。保证当路径不为根目录“$\texttt{/}$”时，路径不以“$\texttt{/}$”结尾。

输出格式

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

样例一

input

6 5
/root /
/duliu /picks
/vfk /vfleaking
/orz/orz/orz /duliu
/otl /duliu/duliu
/vfk/sb /vfleaking
/vfk/sb/nothing/nothing
/orz
/orz/orz/orz
/qaq
/otl

output

/vfleaking/nothing/nothing
/orz
/picks
/qaq
/picks/duliu

explanation

创建的快捷方式分别为：

• $\texttt{/root} \rightarrow \texttt{/}$
• $\texttt{/duliu} \rightarrow \texttt{/picks}$
• $\texttt{/vfk} \rightarrow \texttt{/vfleaking}$
• $\texttt{/orz/orz/orz} \rightarrow \texttt{/picks}$
• $\texttt{/otl} \rightarrow \texttt{/picks/duliu}$
• $\texttt{/vfleaking/sb} \rightarrow \texttt{/vfleaking}$

样例二

input

2 3
/ba/la /
/w/o/w /w
/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la
/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba
/w/o/w/o/w/o/w/o

output

/
/ba
/w/o

样例三

见样例数据下载

限制与约定

对于所有数据，输入中路径字符串总长度不会超过 $5 \times 10^5$。

时间限制：$1 \texttt{s}$

空间限制：$256 \texttt{MB}$

为了防止有些同学看晕了，我还是再罗嗦几句。下面的路径名都是非法的：

• $\texttt{/orz/}$
• $\texttt{/orz//otl}$
• $\texttt{/233}$ （注意，只能含有小写英文字母）

下面的路径名都是合法的：

• $\texttt{/}$
• $\texttt{/orz/otl/oorrzz/oottll}$
• $\texttt{/a}$

下载

样例数据下载