题目背景

题目来源：https://hsin.hr/hio2023/。

题目描述

一个春天的傍晚，天气异常温暖，两位市民出现在莫斯科的牧首池塘边。第一位不是别人，正是编辑米哈伊尔·亚历山德罗维奇·别尔利奥兹 (Mihail Aleksandrovič Berlioz)，而另一位是名叫“无家汉” (Bezdomni) 的年轻诗人。他们每人都带着一个长度为 $N$ 的字符串。

很快，一位神秘的黑魔法专家，沃兰德 (Woland) 教授，也加入了他们，并说道：

• “先生们，你们的字符串非常有趣，我一眼就能看出它们是否 相近！”

一次操作的定义是：选择一个字符串中的两个相邻字母，并将这两个字母都在字母表中循环前移一位。例如，将字母对 “ab” 变为 “bc”，或是将 “qz” 变为 “ra”。如果两个字符串可以通过对它们各自进行若干次操作后变得完全相同，那么这两个字符串就被认为是 相近的 (bliskima)。

• “那当然了，教授，您在胡说八道。判断两个字符串是否相近可是个出了名的难题。”

• “不不，米哈伊尔·亚历山德罗维奇，您搞错了，我这就向您证明！瞧好了，我现在就告诉您，您的两个字符串是否相近。然后，您再对您的字符串进行 $Q$ 次修改。在每一次修改之后，我都会再次判断它们是否相近。”

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

输入格式

第一行包含两个正整数 $N$ 和 $Q$，分别表示字符串的长度和修改的次数。

第二行是一个长度为 $N$ 的字符串，属于别尔利奥兹。

第三行是一个长度为 $N$ 的字符串，属于“无家汉”。

接下来 $Q$ 行中的第 $i$ 行，包含一个数字 $p_i$ 和一个字符 $c_i$，表示在第 $i$ 次修改中，别尔利奥兹将自己字符串中第 $p_i$ 个字母改为了 $c_i$。

输出格式

在第一行，如果初始的两个字符串是相近的，请输出 “da”，否则输出 “ne”。

在接下来 $Q$ 行中的第 $i$ 行，你需要根据在别尔利奥兹的字符串进行了第 $i$ 次修改后两个字符串是否相近，来输出 “da” 或 “ne”。

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 分）：没有其他额外限制。