该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意：

最初只有一份编号为 $1$ 的文本，内容为 $s$。依次处理以下操作：

• COPY k：复制第 $k$ 份文本，得到一份新的文本。新编号等于已有文本份数加 $1$。复制完成后，两份文本相互独立，之后修改其中一份不会改变另一份。
• APPEND k t：将字符串 $t$ 接到第 $k$ 份文本的末尾。
• CUT k l r：第 $k$ 份文本只保留当前第 $l$ 个到第 $r$ 个字符，包括两端；保留部分成为该份文本的新内容。
• COMPARE a b：比较第 $a$、$b$ 份文本的字典序，前者较小输出 -1，相同输出 0，前者较大输出 1。
• FIND k c：输出字符 $c$ 在第 $k$ 份文本中第一次出现的位置；没有出现则输出 $0$。

字符位置从 $1$ 开始编号。字典序比较从左到右找到第一个不同字符，字母靠前的文本较小；一方是另一方的完整前缀时，较短的一方较小。

输入格式：

第一行一个整数 $q$（$1 \le q \le 2000$），表示操作次数。

第二行一个字符串 $s$（$1 \le |s| \le 2000$），表示初始文本。

接下来 $q$ 行，每行给出一条上述操作。所有被引用的文本编号都已经存在。对于额外参数：

• APPEND k t 中，字符串 $t$（$1 \le |t| \le 2000$）表示追加内容。
• CUT k l r 中，整数 $l$、$r$（$1 \le l \le r \le m$）表示保留范围，$m$ 为该文本操作前的长度。
• FIND k c 中，$c$ 是一个小写英文字母。

所有文本和追加字符串仅由小写英文字母组成。保证任意时刻，每份文本的长度均不超过 $2000$。

输出格式：

对每条 COMPARE 或 FIND 操作输出一行结果。其他操作不产生输出；没有此类询问时不输出内容。

样例：

样例输入：

11
ab
COPY 1
APPEND 1 c
COMPARE 1 2
FIND 2 c
APPEND 2 d
COMPARE 1 2
CUT 2 2 3
COPY 2
APPEND 3 a
FIND 3 d
COMPARE 2 3

样例输出：

1
0
-1
2
-1

样例解释：

修改第 $1$ 份文本后，第 $2$ 份仍为 ab。最后三份文本分别为 abc、bd、bda，其中 bd 是 bda 的完整前缀。