One spring, during an unusually warm twilight, two citizens appeared at the Patriarch's Ponds in Moscow. The first was none other than the editor Mikhail Alexandrovich Berlioz, while the second was a young poet named Bezdomny. Each had with them their own string of letters of length $N$...
Soon, a mysterious specialist in black magic, Professor Woland, joined them and said: - Gentlemen, you have very interesting strings of letters, and I can immediately tell at a glance whether they are close or not!
A move consists of choosing two adjacent letters in a string and shifting both letters cyclically forward in the alphabet, for example, transforming the pair of letters "ab" into the pair "bc", or the pair "qz" into the pair "ra". Two strings are considered close if it is possible to make them equal by applying moves to both strings.
- Of course, Professor, you are talking nonsense. The problem of determining the closeness of two strings is notoriously difficult.
- Oh no, you are mistaken, Mikhail Alexandrovich, and I will prove it to you right now! Here is how it is: I will tell you now whether your strings are close or not, and then you will make $Q$ changes to your string. After each change, I will determine the truth of the closeness of your strings.
- Very brave, Professor, truly, very brave... so let us begin!
Input
The first line contains the natural numbers $N$ and $Q$, the length of the strings and the number of changes, respectively.
The second line contains a string of characters of length $N$, the string belonging to Berlioz.
The third line contains a string of characters of length $N$, the string belonging to Bezdomny.
The $i$-th of the following $Q$ lines contains the number $p_i$ and the character $c_i$, which indicates that in the $i$-th change, Berlioz changed the $p_i$-th letter to $c_i$.
Output
In the first line, you must print "da" if the initial strings are close, or "ne" if they are not.
In the $i$-th of the following $Q$ lines, you must print whether the strings are close after Berlioz's $i$-th change.
Subtasks
In all subtasks, $1 \le N \le 1\,000\,000$ and $0 \le Q \le 1\,000\,000$ hold.
| Subtask | Points | Constraints |
|---|---|---|
| 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 | No additional constraints. |
Examples
Input 1
3 1 bbc ced 1 a
Output 1
ne da
Input 2
6 0 berlio pjesni
Output 2
da
Note
In the first example, after the change, the words are close by the following moves: abc $\to$ bcc $\to$ cdc $\to$ dec $\to$ dfd ced $\to$ dfd