题目背景

题目来源：https://hsin.hr/hio2023/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

在春天的一个异常温暖的午后，莫斯科的 Patrijaršijskim Ribnjačama 出现了两位市民。第一位不是别人，正是编辑 Mihali Aleksandrovic Berlioz ，而另一位则是一位被称为“Bezdomni 无家可归者”的年轻诗人。他们各自带着一串长度为 $N$ 的字母。

不久之后，一位神秘的黑色魔法专家，Woland 教授加入了他们，并说道：“先生们，你们手中的字母串非常有趣，我能立刻判断出它们是否相近！”他解释道，通过选择一串字母中连续的两个字母，并将它们按照字母表顺序向前循环移动，例如将 ab 变为 bc，或者 qz 变为 ra，如果在两串字母上应用这一操作后，它们能够变得相同，那么这两串字母就被认为是相近的。

“当然，教授，您在说胡话。判断两串字母是否相近的问题显然很难。”

“不，Mihali Aleksandrovic，你错了，我现在就要向你证明这一点！这样吧，我现在就来告诉你，你们的字母串是否相近，然后你们再对自己的字母串进行 $Q$ 次变换。每次变换后，我都会再次判断你们字母串的相近性是否属实。”

“教授，您真是非常勇敢，确实非常勇敢……那么，我们开始吧！”

输入格式

第一行包含自然数 $N$ 和 $Q$，分别表示字符串的长度和变化次数。

第二行是一个长度为 $N$ 的字符数组，属于 Berlioz。

第三行也是一个长度为 $N$ 的字符数组，属于 Bezdomni（无家可归者）。

接下来的 $Q$ 行中，每行包含一个整数 $p$ 和 $p$ 个字符，表示在第 $i$ 次变化中，Berlioz 改变了第 $p_i$ 个字符到某个新字符。

输出格式

第一行需要输出 da（如果初始字符串是相近的）或 ne（如果不是相近的）。

接下来的 $Q$ 行，对于每一次 Berlioz 的变化，需要输出变化后两个字符串是否还是相近的。

3 1
bbc
ced
1 a

ne
da

6 0
berlio
pjesni

da

提示

【样例解释】

在第一个示例中，更改后，单词在后续步骤中相近关系：

• $\tt abc \to bcc \to cdc \to dec \to dfd$
• $\tt ced \to dfd$

【数据范围】

对于所有子任务，都有 $N$ 和 $Q$ 的取值范围限制：$1 \leq N \leq 1\times 10^6$ 和 $0 ≤ Q ≤ 1\times 10^6$。

• 子任务 1（7 分）：$Q=0$，$N\leq 5$；
• 子任务 2（8 分）：$Q=0$，$N\leq 1000$；
• 子任务 3（13 分）：$Q=0$；
• 子任务 4（12 分）：$Q\leq 100000$，$N\leq 5$；
• 子任务 5（17 分）：$Q\leq 100000$，$N\leq 1000$；
• 子任务 6（43 分）：没有其他额外限制。