[AdditionalFile5489.zip](file://AdditionalFile5489.zip?type=additional_file)

#5489. 「COI 2023」Bliskost

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2023 T1「Bliskost」

在一个温暖春日的黄昏时分，有两个男人出现在主教湖畔。一位正是米哈伊尔·亚历山德罗维奇·别尔利奥兹，而另一个年轻些的则是一位常被称为「无家汉」的诗人。他们每人都带着一个由 $N$ 个字母组成的序列……

一位黑魔法专家，沃兰德教授，很快加入了他们并说道：

• 先生们，你们的字母序列真的很有趣，而且我能轻易地判断出它们是否相近！

一次移动被定义为选择两个相邻的字母并将它们都循环移位一位。例如，将字母对 ab 变为 bc，或将 qz 变为 ra。如果两个字母序列可以通过对它们双方都进行一系列操作后变得相等，那么它们就被认为是相近的。

• 教授，您肯定是在开玩笑。判断两个这样的序列是否相近是出了名的难题。
• 哦不，米哈伊尔·亚历山德罗维奇，您才是搞错了的那个人，而我将证明这一点！听好了，我现在就告诉您您的两个序列是否相近，并且，您还要将您的序列更改 $Q$ 次。每次更改后，我都会告诉您它们是否相近！
• 您真有胆量，教授，确实有胆量……那么，我们开始吧？

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别是序列的长度和别尔利奥兹将要进行的更改次数。

第二行包含一个长度为 $N$ 的字母序列，这是属于别尔利奥兹的序列。

第三行包含一个长度为 $N$ 的字母序列，这是属于无家汉的序列。

接下来的 $Q$ 行中，第 $i$ 行包含一个数字 $p_{i}$ 和一个字母 $c_{i}$，描述了在第 $i$ 次更改中，别尔利奥兹会将第 $p_{i}$ 个字母变为 $c_{i}$。

输出格式

在第一行，如果初始序列是相近的，你应该输出 da，否则输出 ne。

在接下来的 $Q$ 行中，第 $i$ 行应根据别尔利奥兹第 $i$ 次更改后序列是否相近，输出 da 或 ne。

样例 1

输入

3 1
bbc
ced
1 a

输出

ne
da

样例 2

输入

6 0
berlio
pjesni

输出

da

数据范围与提示

对于所有输入数据，满足 $1 \leq N \leq 1000000$ 且 $0 \leq Q \leq 1000000$。

详细子任务附加限制及分值如下表所示：