Задача №111535. День без гаджетов
Вася участвовал в недавнем эксперименте: проведи 8 часов без гаджетов. Для того чтобы убить время, он стал проделывать со случайной строкой, состоящей только из нулей и единиц, следующую процедуру. Каждый ноль этой строки он заменял на строку S, тоже состоящую из нулей и единиц, а каждую единицу — на строку T, опять же из нулей и единиц. Строки S и T он выписал заранее. С полученной строкой он опять проделывал ту же самую процедуру, не меняя при этом строки S и T. За 8 часов он успел таким образом сделать K преобразований.
Помогите Васе определить, на каком по счету месте в итоговой строке окажется N-я единица, если гарантируется, что N единиц в этой строке есть. Нумерация символов в строке, как и подсчет единиц, ведется с единицы.
В первой строке входного файла находятся числа K (0 ≤ K ≤ 100 000) и N (1 ≤ N ≤ 1018). Во второй строке файла находится исходная строка. В третьей — строка S, в четвертой — строка T. Длина каждой из строк не превосходит 1 000 символов.
Выведите одно число — номер N-й единицы в итоговой строке. Гарантируется, что ответ не превосходит 1018.
1 3
01
10
11
4
3 10
0
101
01
17
Тесты состоят из пяти групп.
- Тесты 1–2, из условия, оцениваются в 0 баллов.
- В тестах этой группы 1 ≤ K ≤ 10, 1 ≤ N ≤ 10, длины строк во входном файле не превосходят 2. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й группы. Эта группа оценивается в 20 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ K ≤ 10, 1 ≤ N ≤ 106, гарантируется, что ответ не превосходит 106. Баллы за тесты этой группы начисляются только при прохождении всех тестов 2-й группы. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ K ≤ 1 000, 1 ≤ N ≤ 107, гарантируется, что ответ не превосходит 107. Баллы за тесты этой группы начисляются только при прохождении всех тестов 3-й группы. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- Баллы за тесты этой группы начисляются только при прохождении всех тестов 4-й группы. Каждый тест оценивается независимо от других.