UOJ Logo Universal Online Judge

UOJ

#13. 【UER #1】跳蚤OS

统计

跳蚤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

样例三

见样例数据下载

限制与约定

测试点编号 $n$ $m$ 其他
1$\leq 200$$\leq 10$保证单个字符串长度不会超过 $40$
2
3
4$\leq 20000$保证每个输入的路径字符串中仅包含一个“$\texttt{/}$”且位于字符串开头。
保证单个字符串长度不超过$15$。
5
6
7$\leq 20000$
8
9
10

对于所有数据,输入中路径字符串总长度不会超过 $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}$

下载

样例数据下载