一个春天的傍晚，在异常温暖的黄昏时分，莫斯科的牧首池塘出现了两位市民。第一位不是别人，正是编辑米哈伊尔·亚历山德罗维奇·柏辽兹（Berlioz），而第二位是年轻的诗人，人称无家可归者（Bezdomny）。他们每人手里都拿着一个长度为 $N$ 的字符串……
很快，神秘的黑魔法专家沃兰德（Woland）教授加入了他们，并说道：
— “绅士们，你们的字符串非常有趣，我一眼就能看出它们是否相似！”
一次操作定义为：选择一个字符串中相邻的两个字母，并将这两个字母在字母表中循环往后移动一位。例如，将字母对 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 \le N \le 1\,000\,000$ 且 $0 \le Q \le 1\,000\,000$。
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 7 | $Q = 0, N \le 5$ |
| 2 | 8 | $Q = 0, N \le 1\,000$ |
| 3 | 13 | $Q = 0$ |
| 4 | 12 | $Q \le 100\,000, N \le 5$ |
| 5 | 17 | $Q \le 100\,000, N \le 1\,000$ |
| 6 | 43 | 无附加限制。 |
样例
输入样例 1
3 1 bbc ced 1 a
输出样例 1
ne da
输入样例 2
6 0 berlio pjesni
输出样例 2
da
说明
在第一个样例中，修改后，柏辽兹的字符串变为 abc。这两个字符串可以通过以下操作变得相同，因此它们是相似的：
abc → bcc → cdc → dec → dfd ced → dfd