Consistency
НОИ 2017, Контрола 2
Time Limit: 0.5s, Memory Limit: 64MiB
Докато сваляше поредния епизод на известен сериал с вампири, Ели се замисли как всъщност знае, че нещото, което сваля, е именно това, а не, примерно, изпълним файл, кликането върху който ще доведе до заличаването на човечеството?

След известно проучване се оказа, че тракер системите ползват умен начин за проверка дали части от файла съвпадат. Сега Ели се зачуди как ли го правят?

Отчасти за да я впечатлите, отчасти защото вие също много искате да гледате серията, а момичето го е страх да цъкне върху файла поради опасността от настъпване на апокалипсис, решавате да напишете програма, която може ефективно да върши това.

За целите на задачата ще считаме файловете за стрингове съставени от главни и малки латински букви, цифри, и символите '+' и '/' (азбуката {'A'-'Z', 'a'-'z', '0'-'9', '+', '/'}).
Вход
На първия ред на стандартния изход ще бъдат зададени целите числа N и M – дължината на два стринга, представляващи два файла. На втория ред ще бъде зададен стринг с дължина N – началното съдържание на първия файл. На третия ред ще бъде зададен стринг с дължина M – началното съдържание на втория файл. И двата стринга ще съдържат само символи от дадената по-горе азбука.

Следва ред, съдържащ цялото число Q – броя промени по файловете или въпроси за "еднаквост", на които трябва да отговорите. Всеки от следващите Q реда ще бъде един от следните:
  • 1 X C – променяме символа на X-та позиция в първия стринг на C
  • 2 Y C – променяме символа на Y-та позиция във втория стринг на C
  • 3 K X Y – питаме дали под-стринговете с дължина K, започващи от X-та позиция в първия стринг и Y-та позиция във втория, са еднакви
Всички индекси в задачата започват от нула.
Изход
За всеки въпрос от тип 3 на отделен ред на стандартния изход изведете "YES", в случай, че под-стринговете са еднакви, или "NO" в противен случай.
Ограничения
  • 1 ≤ N, M, Q ≤ 100,000
  • 0 ≤ X < X + KN
  • 0 ≤ Y < Y + KM
Примерен Вход Примерен Изход
30 27 Z29vZGpvYmZvcmRlY29kaW5ndGhpcw Y29kaW5naXNlbGx5c3Bhc3Npb24 10 3 8 16 0 3 10 16 0 1 25 X 3 10 16 0 2 8 d 3 10 16 0 1 0 Y 3 3 0 0 3 2 28 20 3 1 28 20 YES NO NO YES YES NO YES
При първото питане искаме да сравним "Y29kaW5n" от първия стринг с "Y29kaW5n" от втория. Тъй като са еднакви, печатаме "YES". Когато пробваме да е малко по-дълъг, обаче, вече имаме разлика: "Y29kaW5ndG" срещу "Y29kaW5naX", затова на втората заявка печатаме "NO". Следват две промени, които заменят 'G'-то на 25-та позиция в първия стринг с 'X' и 'a'-то на 8-ма позиция във втория на 'd'. Така вече под-стринговете с дължина 10 също са еднакви.
Мрън!