题目描述

李明正在学习使用文本编辑器软件 Vim。与 Word、VSCode 等常用的键鼠配合使用的文本编辑器不同，Vim 采用了键盘操控＋模式切换的设计。初始时用户处于普通模式，此时用户可以通过键盘输入命令执行光标移动等操作，或者输入特定命令进入到编辑模式；而在编辑模式中，用户可以从当前光标位置开始，向文本输入内容，然后按 ESC 键切换回普通模式。

李明学习到了普通模式的如下指令。其中 $(𝑟, 𝑐)$ 为当前光标的位置，即第 $𝑟$ 行第 $𝑐$ 列，$𝐿_𝑟$ 表示第 $𝑟$ 行当前的长度，$𝑅$ 为当前文本总行数，数学符号 $\min\{𝑥, 𝑦\}$ 表示 $𝑥$ 与 $𝑦$ 的最小值，例如 $\min\{2,4\} = 2$：

从编辑模式按 ESC 键切换回普通模式时，光标位置位于编辑模式插入的最后一个字符处（假定每次进入编辑模式后至少向文本中插入一个字符）。初始时，Vim 处于普通模式，光标位置为 $(1,1)$。假设当前文本如下，光标位置用粗斜体＋下划线＋红色标注。李明的键盘输入序列为 jlliHello^kIWorld^，其中 ^ 用于表示 ESC 键：

对于李明的键盘操作，jll 表示下移一格再右移两格，光标按 A→H→I→I 的顺序移动（其中第二次右移因为触及本行末尾无事发生）。此时光标位置为 $(2,2)$，即第 $2$ 行第 $2$ 列。Vim 编辑器界面如下：

之后 iHello^ 表示从当前光标位置进入编辑模式，将插入的内容 Hello 置于此时光标位置 I 的左侧，然后按 ESC 键返回普通模式。此时光标位置为 $(2,6)$，指向此次插入内容 Hello 的最后一个字符 o，Vim 编辑器界面如下。另外需注意，指令按键（例如本段示例中的小写字母 l）仅在普通模式下才表示编辑器控制指令，在编辑模式中则作为文本内容输入：

然后按 k 键将光标移至上一行。由于上一行的长度小于当前光标所在的列数，因此光标被移到了上一行的末尾。此时光标位置为$(1,3)$：

最后一段 IWorld^ 表示，按 I 键将光标移至本行最左侧的字母 A 处，进入编辑模式并将文本 World 插入到字母 A 的左端，然后按 ESC 退出编辑模式，光标停在插入的最后一个字母 $d$ 处，坐标为 $(1,5)$。

已知文本编辑器的初始内容，以及李明的键盘操作序列，你需要输出操作结束后，Vim 编辑器中的文本内容，以及最终光标所在的位置。

输入格式

输入文件的第一行是一个正整数𝑁，表示初始时编辑器中文本的行数；

之后 $𝑁$ 行，每行一个仅包含大小写字母的字符串，表示改行初始时的内容；

之后一行为一个仅包含大小写字母和 ^ 的字符串，表示李明的键盘操作序列。输入保证操作序列结束后 Vim 处于普通模式，每次进入编辑模式时至少插入一个字符。

输出格式

输出文件共 $𝑁 + 1$ 行。

前 $𝑁$ 行依次为操作结束后文本编辑器中每一行的内容，

最后一行为两个正整数 $𝑟, 𝑐$，表示操作结束后光标的位置。

样例输入1

3
ABC
HI
OPQRS
jlliHello^kIWorld^

样例输出1

WorldABC
HHelloI
OPQRS
1 5

样例输入2

3
ABC
HI
OPQRS
jlliHello^kIWorld^jAXyz^jhhaUvw^

样例输出2

WorldABC
HHelloIXyz
OPQUvwRS
3 6

说明

数据范围

初始时第 $𝑖$ 行的长度为 $𝐿_𝑖$，操作序列的总长度为 $𝐿_𝐶$。所有数据均满足：

$1 ≤ 𝑁 ≤ 100$，

$1 ≤ 𝐿_𝑖 ≤ 100$，

$1 ≤ 𝐿_𝐶 ≤ 10000$。

测试数据的分布如下：

注意区分数字 1、小写字母 l 与大写字母 I。本题中光标右移指令为小写字母 l，行首插入的指令为大写字母 I。