小A的文本编辑器

时间限制：1000MS 512MB

题目描述

小A最近新学习如何使用一个类似 Vim 的文本编辑器，他请小B想了个办法考考自己有没有记住用法。

小B提供给他一个 $n$ 行的文本，行号从 $1$ 到 $n$。每一行的字符也从$1$开始编号。刚开始时，光标位于文本的第 $1$ 行 第 $1$ 个字符上。

小B随后提供了 $m$ 个命令，要求小A按照顺序模拟运行全部命令。在每一个命令执行完成后，都需要输出当前光标所在的行号、列号以及该位置上的字符。

文本特性说明：

1. $n$ 行文本仅包含非空格的可打印字符（数字、字母、标点等）。
2. 保证每一行至少有一个字符。

命令行为说明

1. 水平移动类

这类命令只改变光标在当前行的列位置，不改变行号。

• h：光标向左移动一格。如果光标已经在行首（第 1 个字符），则位置不变。
• l(小写L)：光标向右移动一格。如果光标已经在当前行的行尾（最后一个字符），则位置不变。
• 0(数字0)：光标直接跳转到当前行的行首（第 1 个字符）。
• $：光标直接跳转到当前行的行尾（最后一个字符）。

2. 垂直移动类

这类命令主要改变行号。在移动到新的一行时，光标的列号遵循**"尽可能保持不变"**的原则：

原则：假设光标原先在第 $c$ 列，移动到目标行后，尽量仍停留在第 $c$ 列。但如果目标行的长度小于 $c$，光标将被强制限制在目标行的最后一个字符上。此后若再进行垂直移动，列号以当前实际位置为准。

• j：光标下移一行。如果已经在最后一行，则保持在最后一行，列号根据上述原则修正。
• k：光标上移一行。如果已经在第一行，则保持在第一行，列号根据上述原则修正。
• gg：光标直接跳转到文本的第一行。
• G：光标直接跳转到文本的最后一行。

3. 跳转指令类

这类命令以冒号:开头，后面紧跟参数，属于特殊的垂直移动，列号处理规则同上。

• :数字（例如:10）：光标跳转到指定的绝对行号。如果输入的行号大于 $n$，则跳转到最后一行；如果小于 $1$，则跳转到第一行。
• :+数字（例如:+5）：光标从当前行向下跳转指定行数。如果目标行号超出了最后一行，则停留在最后一行。
• :-数字（例如:-3）：光标从当前行向上跳转指定行数。如果目标行号超出了第一行，则停留在第一行。

输入描述

第一行包含两个整数 $n, m$ ($1 \le n \le 1000 , 1 \le m \le 10^4$)，分别表示文本行数和命令条数。接下来 $n$ 行，每行包含一个不含空格的字符串，表示文本内容。接下来 $m$ 行，每行包含一个命令字符串。

输出描述

输出共 $m$ 行。每行输出三个内容，用空格隔开：行号 列号 字符。

输入样例

3 8
hello
abc
programming
l
l
j
k
$
j
j
h

输出样例

1 2 e
1 3 l
2 3 c
1 3 l
1 5 o
2 3 c
3 3 o
3 2 r

输入样例

5 15
A
1234567890
B
1234567890
C
j
$
j
j
$
k
j
$
gg
j
$
G
k
$
:3

输出样例

2 1 1
2 10 0
3 1 B
4 1 1
4 10 0
3 1 B
4 1 1
4 10 0
1 1 A
2 1 1
2 10 0
5 1 C
4 1 1
4 10 0
3 1 B

数据范围

1. 关于边界：
   • 在第 1 行执行k或:-，光标停留在第 1 行。
   • 在第 $n$ 行执行j或:+，光标停留在第 $n$ 行。
   • 水平移动不会换行（在行尾按l不会去下一行）。
2. 数据范围：
   • 文本行数 $n \le 1000$
   • 命令数 $m \le 10^{4}$
   • 每行字符串长度不超过 $1000$
   • :命令后的数字的绝对值不超过 $1000$