Problem Description

On an unusually warm spring afternoon, two citizens appeared at Patrijaršijskim Ribnjačama in Moscow. The first was none other than the editor Mihali Aleksandrovic Berlioz, and the second was a young poet known as "Bezdomni" (the homeless). Each of them carried a string of letters of length $N$.

Shortly after, a mysterious black magic expert, Professor Woland, joined them and said, "Gentlemen, your strings of letters are quite interesting. I can immediately determine if they are close!" He explained that by selecting two consecutive letters in a string and cyclically moving them forward in the alphabet, such as changing ab to bc, or qz to ra, if applying this operation on both strings could make them identical, then the two strings are considered close.

"Of course, Professor, you're talking nonsense. The problem of determining if two strings are close is obviously difficult."

"No, Mihali Aleksandrovic, you're wrong. I'm about to prove it to you! Let me tell you now if your strings are close, and then you will make $Q$ transformations to your strings. After each transformation, I will again determine if your strings are still close."

"Professor, you are indeed very brave... Let's begin!"

Input Format

The first line contains the natural numbers $N$ and $Q$, representing the length of the strings and the number of transformations, respectively.

The second line is a character array of length $N$, belonging to Berlioz.

The third line is also a character array of length $N$, belonging to Bezdomni.

The next $Q$ lines each contain an integer $p$ and $p$ characters, indicating that in the $i$-th transformation, Berlioz changed the $p_i$-th character to a new character.

Output Format

The first line should output da if the initial strings are close, or ne if they are not.

The next $Q$ lines, for each transformation by Berlioz, should output whether the two strings are still close after the transformation.

Sample Input and Output

Input Sample #1

3 1
bbc
ced
1 a

Output Sample #1

ne
da

Input Sample #2

6 0
berlio
pjesni

Output Sample #2

da

Notes

[Sample Explanation]

In the first example, after the change, the closeness relationship in subsequent steps:
- $\tt abc \to bcc \to cdc \to dec \to$
- $\tt ced \to$

[Data Range]

For all subtasks, the values of $N$ and $Q$ are restricted: $1 \leq N \leq 1\times 10^6$ and $0 ≤ Q ≤ 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 additional restrictions.

见题面 Input 部分

见题面 Output 部分