P10753 [COI 2023] Bliskost

Source: 。

On a spring evening, the weather was unusually warm, and two citizens appeared by the Patriarch's Ponds in Moscow. The first was none other than the editor Mihail Aleksandrovič Berlioz, and the other was a young poet called "Bezdomni" (pinyin: Wujiahan). Each of them carried a string of length $N$. Soon, a mysterious black magic expert, Professor Woland, also joined them and said: - "Gentlemen, your strings are very interesting. I can tell at a glance whether they are **close**!" One operation is defined as follows: choose two adjacent letters in a string, and shift both letters one step forward in the alphabet cyclically. For example, change the pair "ab" into "bc", or change "qz" into "ra". If two strings can be made exactly the same after performing some number of operations on each of them, then the two strings are considered **close (bliskima)**. - "Of course, Professor, you are talking nonsense. Deciding whether two strings are close is a famous hard problem." - "No, no, Mihail Aleksandrovič, you are mistaken, and I will prove it to you right now! Watch carefully: I will now tell you whether your two strings are close. Then you will make $Q$ modifications to your string. After each modification, I will again decide whether they are close." - "You are really brave, Professor, indeed, very brave... then, let's begin!"

The first line contains two positive integers $N$ and $Q$, representing the length of the strings and the number of modifications. The second line is a string of length $N$, belonging to Berlioz. The third line is a string of length $N$, belonging to "Bezdomni" (pinyin: Wujiahan). In the next $Q$ lines, the $i$-th line contains an integer $p_i$ and a character $c_i$, meaning that in the $i$-th modification, Berlioz changes the $p_i$-th letter of his string to $c_i$.

On the first line, if the two initial strings are close, output "da"; otherwise output "ne". On the next $Q$ lines, on the $i$-th line, after the $i$-th modification to Berlioz's string, output "da" or "ne" depending on whether the two strings are close.

**Sample Explanation** In the first example, after the changes, the words are close in the following steps: - $\tt abc \to bcc \to cdc \to dec \to dfd$ - $\tt ced \to dfd$ **Constraints** For all subtasks, the ranges of $N$ and $Q$ are: $1 \leq N \leq 1\times 10^6$ and $0 \leq Q \leq 1\times 10^6$. - Subtask 1 (7 points): $Q=0$, $N\leq 5$. - Subtask 2 (8 points): $Q=0$, $N\leq 1000$. - Subtask 3 (13 points): $Q=0$. - Subtask 4 (12 points): $Q\leq 100000$, $N\leq 5$. - Subtask 5 (17 points): $Q\leq 100000$, $N\leq 1000$. - Subtask 6 (43 points): no other additional constraints. Translated by ChatGPT 5