근접성

어느 봄날, 유난히 따뜻했던 저녁에 M*skva의 총대주교 연못가에 두 남자가 나타났다. 한 명은 편집자 미할리 알렉산드로비치 베를리오즈였고, 다른 한 명은 베즈도므니라는 젊은 시인이었다. 두 사람은 각자 길이가 $N$인 문자열을 하나씩 가지고 있었다.

얼마 뒤 흑마술 전문가 볼란드 교수가 다가와 말했다.

"여러분의 문자열은 매우 흥미롭군요. 저는 한눈에 두 문자열이 가까운지 아닌지 알아볼 수 있습니다!"

한 번의 연산은 한 문자열에서 연속한 두 문자를 골라, 두 문자를 모두 알파벳 순서에서 순환적으로 한 칸씩 앞으로 옮기는 것이다. 예를 들어 ab는 bc가 되고, qz는 ra가 된다. 두 문자열에 연산을 적용해서 두 문자열을 같게 만들 수 있으면 두 문자열은 가깝다고 한다.

"교수님, 그건 헛소리죠. 두 문자열이 가까운지 판별하는 문제는 악명 높을 만큼 어렵습니다."

"아닙니다, 미할이 알렉산드로비치. 착각하고 계시는군요. 제가 직접 증명해 보이죠! 지금 두 문자열이 가까운지 말씀드리겠습니다. 그 다음 여러분이 문자열을 $Q$번 바꾸시면, 매번 바뀔 때마다 두 문자열이 가까운지 알려드리겠습니다."

"대단히 대담하시군요, 교수님. 그럼 시작해 봅시다!"

첫째 줄에 자연수 $N$과 $Q$가 주어진다. 각각 문자열의 길이와 변경 횟수이다.

둘째 줄에는 베를리오즈의 길이 $N$인 문자열이 주어진다.

셋째 줄에는 베즈도므니의 길이 $N$인 문자열이 주어진다.

이어지는 $Q$개의 줄에는 정수 $p_i$와 문자 $c_i$가 주어진다. 이는 $i$번째 변경에서 베를리오즈가 $p_i$번째 문자를 $c_i$로 바꾸었다는 뜻이다.

첫째 줄에 처음 두 문자열이 가까우면 da, 가깝지 않으면 ne를 출력한다.

이어지는 $Q$개의 줄에는 베를리오즈의 문자열을 $i$번째로 바꾼 뒤 두 문자열이 가까운지를 같은 형식으로 출력한다.

첫 번째 예제에서 변경 후의 두 단어는 다음 연산들로 가까워진다. abc → bcc → cdc → dec → dfd, 그리고 ced → dfd.