Кот Матроскин ждёт невероятно важное сообщение от своих родственников из Котинска. Но так как его родственники очень тревожные и боятся, что сообщение будет перехвачено, они его закодировали.
Кодирование, которое использовали коты, основано на том, что если какая-то подстрока уже встречалась ранее в строке, то на неё можно сослаться, указав, на сколько нужно сместиться относительно текущего элемента, чтобы попасть на первый символ нужной нам подстроки, и размер подстроки. Закодированное сообщение представляет из себя строку, в которой последовательно идут тройки элементов:
- первый элемент тройки — цифра, на которую нужно сместиться влево в раскодированной части исходной строки, чтобы получить первый символ повторяющейся ранее подстроки;
- второй элемент тройки — цифра, сколько символов нужно забрать (размер подстроки);
- третий элемент — буква, которая будет стоять за скопированной подстрокой.
Пример: закодированная строка 00a00b00c33d. Исходная строка будет строиться следующим образом:
- Изначально у нас пустая строка «».
00a: смещаемся на 0 символов влево и копируем подстроку длиной 0, после неё ставим символ a. Получилась строка «a».00b: получилась строка «ab».00c: получилась строка «abc».33d: смещаемся на 3 символа влево и копируем подстроку длиной 3, после неё ставим символ d. Получилась строка «abcabcd».
«abcabcd» — раскодированная строка.
Матроскин получил одно и то же закодированное сообщение от двух родственников, но проблема в том, что оба родственника допустили по одной ошибке в своих кодах. Кот уже выяснил, что оба родственника ошиблись в записи третьего элемента одной из троек (каждый в своей тройке). Помогите Матроскину восстановить сообщение.
Полученные сообщения от родственников из Котинска:
00a00a00b00c31c11b73b00e00f00a00a11b00c41c00c51c73e00f00a
Примечание: подстрокой называется непрерывная последовательность символов исходной строки. Например, «a», «bc» — будут подстроками для строки «abc».