Description

至于你问为什么要出这个题，可能是出题人想报复社会了。

Git 是一个分布式的版本控制系统，其底层可以看作一个基于有向无环图（DAG）的文件快照系统。

在本题中，你需要实现一个简化的内存版 Git 系统。为了以防你没有用过 Git，我们简单讲解一下：

系统内部维护三个核心区域：

1. 工作区：当前内存中的文件集。
2. 暂存区：由 $\texttt{add}$ 指令添加、等待提交的文件修改集。
3. 版本库：保存所有历史提交、分支指针以及当前位置指针，定义为 $\texttt{HEAD}$。

接下来是一个''简单''的文档。

定义文件标识与存储：每个文件由路径唯一标识。文件路径均以 $\texttt{/}$ 开头（例如 $\texttt{/src/a.cpp}$）。初始时，工作区、暂存区与版本库均为空。

接下来你要处理 $\texttt{commit}$ 指令逻辑：第 $k$ 次成功执行的 $\texttt{commit}$ 指令，其生成的 Commit 提交编号固定为整数 $k$（从 $1$ 开始递增）。

系统初始默认拥有一个名为 $\texttt{main}$ 的分支。$\texttt{HEAD}$ 指针初始指向 $\texttt{main}$ 分支；但此时 $\texttt{main}$ 不指向任何 Commit（版本库为空）。

当 $\texttt{HEAD}$ 指向某个分支名时，称系统处于分支状态。当 $\texttt{HEAD}$ 直接指向某个具体 Commit $k$ 时，称系统处于游离状态。

你需要按顺序处理 $N$ 条指令：

1. $\texttt{add <path> <content>}$: 其作用为将路径为 $\texttt{<path>}$ 的文件内容设置为 $\texttt{<content>}$ 并覆盖写入暂存区。若该文件在暂存区不存在则新建。该指令仅影响暂存区，不改变工作区已有的其他文件，也不生成 Commit。
2. $\texttt{commit -m <message>}$: 其作用为将当前暂存区的全部文件快照持久化，生成编号为 $k$ 的新 Commit。新 Commit 的父节点指向当前 $\texttt{HEAD}$ 所指向的 Commit（若当前无任何 Commit，则无父节点）。若 $\texttt{HEAD}$ 处于分支状态（如指向 main），则该分支指针向前移动，指向新 Commit $k$；若 $\texttt{HEAD}$ 处于游离状态，则 $\texttt{HEAD}$ 本身直接改变指向，指向新 Commit $k$。提交成功后，工作区同步更新为该提交的最终快照，并清空暂存区。若暂存区没有任何文件改动（即暂存区为空），不生成新 Commit，单行输出：$\texttt{Nothing to commit}$。
3. $\texttt{branch <name>}$: 其作用为在当前 $\texttt{HEAD}$ 所指向的 Commit 位置上，创建一个名为 $\texttt{<name>}$ 的新分支指针。该操作仅创建分支指针，不改变 $\texttt{HEAD}$ 当前的指向状态。若名为 $\texttt{<name>}$ 的分支已存在，单行输出：$\texttt{Branch already exists}$；若当前版本库为空（尚无任何 Commit），单行输出：$\texttt{No commit yet}$。
4. $\texttt{checkout <target>}$: 其作用为将系统状态重置到指定的 $\texttt{<target>}$。$\texttt{<target>}$ 可以是分支名，也可以是 Commit $k$（整数）。将工作区和暂存区的内容完全替换为目标 Commit 时的文件快照，清空未提交的所有修改。若 $\texttt{<target>}$ 是分支名，$\texttt{HEAD}$ 指向该分支；若 $\texttt{<target>}$ 是 Commit $k$，$\texttt{HEAD}$ 切换为游离状态，直接指向该 Commit。若目标分支或 Commit $k$ 不存在，单行输出：$\texttt{Target not found}$。
5. $\texttt{status}$: 其作用为查询并打印当前工作区的文件状态。你需要按文件路径的字典序升序输出工作区中的所有文件，每行格式为：$\texttt{<path> <content>}$。若当前工作区不包含任何文件，单行输出：$\texttt{Empty working directory}$。
6. $\texttt{log}$: 其作用为从当前 $\texttt{HEAD}$ 指向的 Commit 开始，沿父节点单链向祖先方向追溯输出历史记录（从新到旧）。每行输出格式为：$\texttt{commit <ID>: <message>}$。若当前未指向任何 Commit（版本库为空），单行输出：$\texttt{No commit log}$。

保证所有命令都是以上 6 种命令的一种。

Format

Input

第一行包含一个整数 $N$ 满足 $1 \leq N \leq 1000$，表示指令的总条数。

接下来 $N$ 行，每行包含一条指令。

所有输入的 $\texttt{<path>}$, $\texttt{<content>}$, $\texttt{<message>}$, $\texttt{<name>}$ 均为不包含空格的字符串，长度不超过 $50$ 个字符。指令格式严格符合规范，$\texttt{<target>}$ 不会出现非法字符。

Output

对于触发了查询（$\texttt{status}$, $\texttt{log}$）或错误提示的操作，单行输出对应内容；成功执行的修改类指令（如 $\texttt{add}$, $\texttt{branch}$, 成功的 $\texttt{commit}$ 与 $\texttt{checkout}$）无任何输出。

Samples

7
status
log
commit -m empty
branch dev
checkout 1
checkout missing
branch main

Empty working directory
No commit log
Nothing to commit
No commit yet
Target not found
Target not found
Branch already exists

11
add /a x
commit -m c1
branch dev
add /a y
commit -m c2
checkout dev
add /b z
commit -m c3
checkout main
status
log

/a y
commit 2: c2
commit 1: c1

Note

下面是该样例的详细说明：

1. $\texttt{status}$：初始化状态，工作区为空，输出 $\texttt{Empty working directory}$。
2. 第 2 $\sim$ 4 行：暂存两个文件并提交，生成 Commit 1，此时 $\texttt{main}$ 指向 Commit 1。
3. $\texttt{branch dev}$：在 Commit 1 上建立 $\texttt{dev}$ 分支指针。
4. 第 6 $\sim$ 7 行：修改 $\texttt{/docs/a.txt}$ 并提交，生成 Commit 2。此时 $\texttt{main}$ 移动至 Commit 2，而 $\texttt{dev}$ 停留在 Commit 1。
5. $\texttt{checkout dev}$：切回 $\texttt{dev}$ 分支，工作区恢复至 Commit 1 状态。
6. $\texttt{checkout 2}$：通过 Commit $k$ 游离切换至 Commit 2，工作区更新至 Commit 2 状态。
7. $\texttt{log}$：自 Commit 2 向祖先追溯，依次打印 Commit 2 与 Commit 1。